You can't delete "Other". It includes data such as iPhone settings, contacts, calendar events, Safari bookmarks/cache/cookies, email and email attachments, SMS/MMS/iMessages, notes, app data, Safari cache, cookies and bookmarks, stored passwords, search index, home screen organization, wi-fi network data, etc. If it's excessive (significantly more than 1GB) you may be able to reduce it by restoring
First try restoring, then restore to your backup. If this doesn't reduce it to a reasonable size, import your photos to your computer (see http://support.apple.com/kb/HT4083), and save other data, then resore as new without using your backup. If your contacts, etc. are synced with iCloud, they will return to your phone when you sign back into your account.
Photos taken using the iPhone camera can be backup/save on your Windows PC. All other photos can be re-sync like your music.
If you have iCloud configured, then yes, you can restore your contacts.
First you need to check if you have contacts in iCloud
Import your camera roll photos to your computer, as explained here: http://support.apple.com/kb/HT4083. If you need to import photo stream photos, save them to the camera roll (tap Edit, tap the photos, tap Share, tap Save to Camera Roll).
Also, as ckuan suggested, go to icloud.com on your computer to confirm that your contacts and other synced data are in your iCloud account.