I know the iPhone App Store is only a few weeks old but I really would like to see some apps that I am used to on the palm. I don't miss the Palm OS, but some of the apps I had on my Treo's were very helpful or fun.
SSH Client – someone wrote a Telnet client, but lets face it if you are a decent network or systems person you really want SSH and not telnet. Or both!
FTP Client – Probably wouldn't use it that much, but a cheap or free client would be a nice to have.
Quicken or an expense program that will export inputed data into a format that Quicken will read. Am I the only one that uses Quicken that wants this? They make a Palm and Windows Mobile version!
Call Recording – This was a must have for me on all my recent phones. Until you have it, you don't realize how much you need to record calls. Especially when dealing with vendors, support people, etc. Had it on my Palm Treo's and my Nokia E61i. I actually didn't use the Treo 750 because it couldn't record calls. Not having this function was a trade off I made when getting the iPhone, but I would hope someone would write a program to do this!
Skype – probably too much to ask for since you can't use VOIP applications via the 3G network, but Skype would be nice!!!
There is probably more, but for now that is all that I can come up with.