I can recommend the palm pre. I have mine since september 09 and it's an awesome platform. WebOS is really convenient (feels much nicer than android in my opinion), is being sold by O2 without contract or sim lock and they legally allow you to run unsigned code. It's running linux and the community is great, lots of homebrew efforts, thousands of homebrew apps and more to come. They just got x11 working now and have compiled firefox successfully. Also it is really easy to patch and modify WebOS through a convenient on device installer called preware which gives you access to the homebrew repositories.
The device normally runs at 500mhz for normal apps and 600mhz for 3d games but with the latest patches pretty much everyone has their phones clocked at 720 or 800mhz. I am running mine at 720 and the impact on battery life is neglectible.
The only troubles I have with the phone are the build quality which is rather flimsy compare to the motorola droid and similar sliders, but if you take care of your gadgets, that shouldn't be a problem. The second annoying thing is that the official app catalogue is still pretty underdeveloped. There are some 900 apps available in Europe as of yet, they have approx. 2000 in the US. The numbers grow larger every day though and apart from Docs2Go (which was promised to be ready on launch, but has turned out to be vapourware now) everything from media support and games to business apps, PIM and IM is pretty much covered and there are dozens of new apps added daily.
I guess it's up to personal preference. I really love having a qwertz keyboard and a touch screen, some people prefer touchscreen only. Same goes for tastes in OS I guess.
Go down to your local phone shop of choice and ask them to let you compare and use a couple of phones for yourself. Don't listen to internet chatter, I have found that information on cellphones especially is highly biased as there is so much fanboyism going on with this.
EDIT: A couple of official games and homebrew games that are awesome!!!
-ScummVM runs flawlessly and looks great on the crisp screen, played through the dig on the train, now I am trying to get through shadow of the templars...
-visualboyadvance runs gba games fairly decently on 500mhz. haven't tried since I overclocked, it's probably way better now, though playing with the touchscreen is weird... well it's got a keyboard as well. I still prefer an actual gba or gp2x though
-Need for speed underground!!! I wasted hours with that. Looks so great with OpenGL ES! Great selection of cars, great soundtrack and smooth gameplay.
-Sims 3 is pretty good, too. Although it bums me out that I can't freely modify my house in the game, except for furniture etc and building upgrades.
-Assassins Creed... yes, assassins creed. I don't need to say more^^. Well I do. It's more of an action jump'n'run style game but still very cool, lotsa freerunning to do and stealthy missions.
-The Settlers has just come out, haven't played that yet but the screenshots and gameplay videos look cool and I'd love to play settlers on the go.
-Driver. Open world mafia driving game, almost like the PC version apparently. Haven't played that either.
... and then there is some sort of GTA clone which looks a lot like San Andreas which I really want to try as well.