I've tried iheartradio but not very impressed. Was gonna try a few others, but then realized it would probably a lot easier and faster to just ask you guys!
I had iheartradio installed, but removed it as well. I use Cherry RPlayer and Slacker (there is also Pandora which is similar to Slacker). There are several other people here have mentioned, but I don't remember the names.
i religiously use pandora as last.fm has sound quality issues and does a terrible job at associating music.
i like iheartradio for lots of reason, the main one being that it doesn't wait for a buffer before playing music. people will recognize this as pausing and skipping, but in an office with a low quality signal, sometimes that pausing and skipping is better than nothing at all.
imusic is a great app for downloading mp3s on the fly too.
Had been looking forward to adding Flycast when it became available for the Droid. Showed up on the Market last night but fails to install. Tried twice. Same result. Too bad.