Does anyone know if you can set up from new and then later restore specific things from iCloud? Like only restore the contacts and messages without restoring everything like settings? I see no way to do this, if you can't that is pretty silly.
Well... Contacts, calendar, bookmarks, notes, reminders, docs, pictures in photo stream... Anything that you can turn on/off in iClouds settings can be restored individually, provided they were synced to iCloud in the first place. Text messages, unfortunately, are part of the general backup, so they can't be restored if you set up your phone as new. If you have a backup on your computer through iTunes, I've heard there are third-party programs that can extract specific info from the backup, including the text messages. I haven't used them myself, so I don't know how well they work.
And iCloud backup does replace iTunes backup. I've restored from iCloud backup, and it does pull down all apps you had installed on your phone from the App store. Of course, it takes a long time to download everything, so if you have the apps on your computer, it's faster to restore from your computer.
As for "other" -- there are several things that can cause them. If you have a substantial amount of "other" left over after a restore, then it's probably one or more apps that are saving their data in a weird way so it gets registered as "other" rather than as part of the apps. Only way to weed them out would be to delete apps one by one, or alternately, delete all apps and install them one by one. Or just accept that there would be some amount of "other" on your phone, and live with it.
And btw, when installing a new app, you need double the amount of space the app normally takes. ie, when installing a 500MB app, you need 1G free. This is because the app is first downloaded as an install file, then it installs, then it deletes the install file.