Reporting for duty!
First rule - you don’t want to go overly tight with your first pair. They need to be tighter than you would go for with trainers, but not so tight that you want to take them off every 5 minutes. Some climbers selling you shoes will try to make you go super tight - don’t listen to them - that’s not needed until you’re using teeny tiny footholds. Try to buy from somewhere you can have a practice climb.
These are a classic entry shoe
http://www.bananafingers.co.uk/evolv-elektra-vtr-p-58.html
As are these
Maybe. I’ve been climbing for 5 years now. My fear of heights has definitely improved during that time (it’s not gone completely though!). The main thing to do is to practice falling safely. Whenever I’m trying a hard move relatively high off the ground, I’ll practice falling safely from it before committing, particularly outdoors, but I’ll do this indoors occasionally as well if I know my head is getting the better of me.
I am much less scared bouldering than climbing on ropes, but that’s mainly because 95% of my climbing is bouldering. Conversely, my wife is really fearless on ropes but can’t get her head around bouldering.
Depends how hard you work at it 
Climbing itself is a terrific workout - better still, it’s fun so (unless you’re actually doing specific training) it doesn’t feel like, say, going to the gym.
Which centre(s) have you been to? Let me know if you ever fancy a DiS climb 
Climbing 