I was used to having fast-dial options on my prior cell phones where you simply hold down a number key to dial a pre-programmed number. The iPhone has a "Favorites" list, but you can't blindly fast-dial due to the lack of keys. Voice-dialing would be an acceptable alternative... there is one 3rd-party solution out, but it requires jailbreak at the moment. They intend to port it to the official SDK when that's released.
I'm also a tad annoyed that I can't sync notes to my Mac. Not a huge issue really.
I also missed the lack of a voice recorder app, though I am now using a 3rd-party solution for that.
Apple's handicaps on ringtones really ticks me off also. I have some professional ringtones (not music) that I really like, and paid for, and can't use them on the iPhone without jumping through hoops with 3rd-party hacks.
I'd also like to be able to put "anything" I like on here. Not just media, as Apple intends, but documents that I may need on-the-go, and the ability to read them. My interim solution is to email them to myself and view via the Mail, but what a nuisance!
That all said, I've had my iPhone since August (I think) and just bought my wife one for her birthday (she got iPhone envy after fiddling with mine for a few minutes!), and I wouldn't trade this for anything now.