Always set up as new. Even when doing updates, especially when jumping from say 9.x to 10.x. iPhone, iPad, always restore and setup as new. Best experience.
You can restore/upload pictures. Contacts, I store them on the iMac and then use iTunes and the iTunes info toggle to "replace contacts on this iPhone," which is an option when your phone is connected to your Mac.
I don't store my contacts in iCloud. I don't store much of anything in iCloud given all the successful hacks. Calendar syncing and reminders is basically what I use it for, and that's only for the extreme convenience; I'd prefer never having to use it.