I read that Google was far more worried about Microsoft at that time. Before the iPhone, it seemed likely that Windows Mobile was going to clean up in the mobile space eventually.
The biggest player at the time (in the US) was RIM. This is why initial Android prototypes were built using the HTC Sooner devices - they wanted to copy the Blackberry and iterate on that layout. Once the iPhone came out, Google had to pivot and copy Apple's glass slab platform instead.
Yes! I think the Sidekick kind of gets forgotten in the story of "next generation smartphones," but it had an on-device app store, an early equivalent to visual voicemail, and arguably one of the better web browsers for its day -- albeit one that worked by having servers somewhere quietly rewriting web sites to work better on the Sidekick's screen. (Hey, it was way better than WML.)
Palm screwed up by failing to replace their ageing OS in time. IIRC they bought the remains of BeOS, built a next-gen PalmOS on top, then panicked in the face of short term cash-flow, sold the development group, tried something else -- failed -- tried to buy it back again, and had to pulled out from under them. At which point the only way out was to buy someone else's OS. They gambled on Windows Mobile (in whatever incarnation it was at the time) then hit the buffers when a frankly rubbish OS running on the Treo phones (which were nice, for thumb-keyboard devices) ran headfirst into the iPhone.
(PalmOS 4+ was a moderately mac-like -- classic original MacOS, not OSX -- handheld operating system. Mac-like and crashed like a 68K Mac too, alas. But if they'd been able to build on their GUI/user interface chops with a modern OS they might have been able to get on board with the touchscreen trend.)
Similarly Psion has a pretty nice device. The psion 5 had a nice keyboard and limiting OS. It supports apps/app stores, but required windows and memberships to be a developer. I pushed them to open up a bit to get more apps, they thought it was a bad idea.
Speaking of which, there is a modern incarnation of that form factor in the shape of the Cosmo Communicator (and it's 1st gen predecessor, the Gemini PDA):
(I have both. Runs Android; desktop Linux port is promised: Sailfish also landed on the Gemini. If you want a modernized Psion 5 this is the biz, although caveat emptor: it's from a very small company and has rough edges on the software side.)
As for the Psion 5, its descendants only recently went away: Symbian (in all its flavours) was developed from the EPOC/32 operating system that it ran, after Psion hit the buffers and Symbian was spun out.
