I don't see how Gmail labels can appear on the iPhone without IMAP. That said I really want to be able to create folders (and rules!) on my iPhone.
I am now trying Yahoo mail and of course its IMAP folders do show on my iPhone.
Unfortunately Yahoo doesn't seem as good at retrieving mail from other (POP3) accounts as Gmail is. For one thing, it re-downloads mail--terrible behavior. At least I was able to specify a different folder for email received via each pop account--and those folders propagate to my iPhone. But actually "getting" Yahoo to check the pop accounts doesn't seem all the dependable. And when I force Yahoo to check "other accounts" it will re-download mail it has already downloaded. Worse, it makes the email's time-stamp the current time (i.e., not the true time the email was received by the POP3 server--grrrr!).
Gmail with folder/label support would be so much nicer!