Happy memories of the Sony/Ericsson P800 here. It was well built, and mine lasted for years. I had it for 2 or 3, then passed it on, after a year in the drawer, to someone who'd broken theirs. He was still using it a couple of years ago.
It was severely limited as to what it could do, because it was UIQ not Nokia's S60 version of Symbian. So every time I saw a brilliant new app in PCW, it would turn out I couldn't run it. I never successfully got Bluetooth to work, although back then this was nothing unusual - and just as likely to be the other devices as the phone. The stylus was horrible to hold, because it was a flat, plastic thingy. But that was OK, because I got a pen with black, blue and stylus nibs. Being Sony, it was also encumbered with Memory Stick. Except not the full size one, that wasn't that much more expensive than SD cards - but Memory Stick Duo (now I think called mini), where you had a smaller card and full-sized adaptor. They were over twice the price of SD cards, which were horrifically expensive at the time.
Still it was amazing for the time, and quite impressively easy to use. You had a flip down keypad, that had little pins behind each key, which simply pressed an electronic version on the touch-screen behind it. So I took that off, and it was lovely to use. You only had to resort to the stylus when you got into more complicated operations, even some menus were just big enough to operate with your finger. And I think I had proper handwriting recognition, instead of the fake letters you had to learn with Palm (although theirs were probably still faster).
The P900s were even better, a friend had one. But I decided on dumb phones, and I think I moved to a Motorola V3 RAZR, which on balance is probably my favourite phone ever. It was only 2 years ago that I jumped back into smartphone land, with a work HTC Wildfire. Clever, but frustrating. Now a Nokia Lumia 710 - Lovely to use, until you try do something complex, then annoying that you can't.
I still think the early iPhones looked much nicer than the later ones. I think the 4 onwards are ugly. The HTC Desire style ones are my current favourite, rubbery stuff on metal for toughness and good grip, and nice and rounded in the hand. Although the childish side of me likes the idea of a big Nokia 920, in bright, bright yellow.