I'm a linux user and rooted my phone just fine.
Yes, it does take a little longer to boot, but how often do you reboot anyways? I hardly ever do.
Also, it is possible to get those stock apps back. Download
THIS and extract it, then look in the apps folder. You should be able to find the apks of the stock apps that you're missing. Just transfer them to your sd card and reinstall them. The only one I don't see in there is the Amazon mp3 app. But I think you can find that apk if you search around the xda CDMA Hero forum a little. If I find it I'll post here where you can find it.