Chuck the Designer,
The discussion of POP vs. IMAP is kind of like do you prefer have a Post Office Box, or a secretary to help sort/keep track of your email.
This article discusses it as well:
http://docs.info.apple.com/article.html?artnum=51729
With IMAP the status of the messages is the same however you access it. If you reply to a message on the iPhone, it shows as having been replied to on web-based email, and on your computer. If you read a message on one, it shows as read on the others as well.
If you have folders on the IMAP server, and move a message to one of those folders, it is in that folder on the other mail clients you access it with.
POP3 was not designed for being accessed from multiple computers, and can have issues like POP locks if you check it at the same time from more than one device. For example leave your computer on checking email, and then check at the same time from the iPhone. This article discusses that issue:
http://docs.info.apple.com/article.html?artnum=307009
If you do not leave messages on the server on all your mail clients, for example your computer and the iPhone, messages received on one, won't be available in other mail clients. To save on storage space, some email providers remove messages when they have been downloaded once from the server, and that will not work when accessing email from both your computer and the iPhone.
As for providers that offer IMAP -
GMail offers both POP3 and IMAP
.Mac offers both POP3 and IMAP
Yahoo offers POP3 for paid email customers, but offers free Push-IMAP for use on the iPhone
AOL offers free IMAP accounts
The four above have settings preconfigured as IMAP on the iPhone with 1.1.3. GMail preconfigures using POP3 with earlier versions of the iPhone software.
Microsoft Exchange servers have IMAP service, but is often disabled by the server admin. This article discusses what needs to be configured on the corporate mail server to work with the iPhone securely:
http://docs.info.apple.com/article.html?artnum=307313
A web search for IMAP email providers brings up a bunch of other options for free and paid IMAP mailbox options. Many ISPs offer both, but sometimes have to be asked about IMAP support.
Hope this helps,
Nathan C.