Well, I decided to try BOTH K-9 and MailDroid... I've discovered that there are things about each of these that I like, and DESPISE. Since I may be doing something wrong, hopefully someone can make me LOVE one of them...
First, MailDroid. It let me set up Gmail, my work POP3, Yahoo, and Hotmail. They all seem to work. Best of all, it seemed to
seamlessly sync with Gmail. That is, if I deleted a message on my phone, I could make it go to "Trash" on the server. If I sent a message, I could make it copy to "Sent" on the server. It just plain works.
BUT... the interface is spartan and clunky, and takes FOREVER to load and sync. If an e-mail has photos in it, forget it. It sits there for sometimes minutes, even if the message and data inside it are small.
So... K-9 (which is the one I want to love). I also was able to connect to all my accounts, and I like the interface. Also seems to poll and load each account's messages faster and more efficiently.
BUT... it seems to have a hate/hate relationship with Gmail. First off, it seems to add labels or extra "IMAP" folders on Gmail, which MailDroid doesn't do. When I delete a message in K-9, Gmail doesn't seem to respond in any way. Read messages aren't even marked as read. I've even loaded the advanced IMAP "lab" thing for Gmail, which should let me move deleted messages to the "Trash". It doesn't work.
So... has anyone managed to tame K-9 to work with Gmail? All I want is the seamlessness I see in either the stock Gmail app, or MailDroid. No extra folders. If I read something, mark it read. If I send something, copy to "Sent". If I delete something, move it to "Trash". That's all I ask.
If I can solve those issues (with your help of course

) then K-9 is definitely the winner.