I rooted and then tried removing some APKs but then the Android App Market wouldn't download any new apps until I reinstalled them all.
Any way around this?
I'm a linux user so I always love trimming down the fat in my desktops/fileserver, however I would advise against this. I went to wipe my phone to start fresh again and nearly bricked it just trying to get the bloatware back on so that it would wipe fine. It was a mess and I barely made it back.
What I would suggest however, is getting Autostarts and working your way through every section and disabling some of the programs. You can get it to not boot up CityID for example, meaning the app is still on the phone safely, but it won't even start the app. Peace of mind knowing the app is still safe for wiping the phone, yet won't boot into RAM and use CPU.
The best way is to change the file extension from .apk to .bak rather than actually deleting the app. If needed, the extension can be fixed later and the app will start up fine.
I've done this quite successfully going both directions.