Whether Android would exist in its current form is kind of irrelevant. We'd have had useful devices anyway, because they'd just have been the next step of the evolution of what was possible and what people wanted. I'd argue that many features of Android / iOS aren't actually the best design, they're just what we happened to end up with.
The PalmPilot devices were pretty good and pre-dated the iPod by many years (IIRC even the Treo with a built in phone pre-dated the iPhone). If Apple had never made their leap from iPod to iPhone, I'm sure the Palm line would have continued its market dominance a lot longer, although by then Blackberry was also becoming a larger player in this market too and also might have lead to the complete demise of Palm even without Apple introducing the iPhone.
Not saying Palm didn't have other problems - the PDB format was quite restrictive, and it was clear that early on Palm didn't even have proper documentation on how it worked as they'd just licensed it from someone else (and ironically, it was actually based on Apple Mac's resource forks).
So, yeah, maybe we would have more Windows phones now, maybe Symbian, maybe RIM, maybe Palm. I'm sure the UIs wouldn't have ended up the same as we have now, but whatever I'm sure the feature set would have ended up similar because that's mostly just the intersection of what's possible to do with current technology and what people want to do.