Also, is killing always optional? I am in basement of the first mission and there is a guard in my way, I'm not sure what I can do about him.
Killing is always optional unless there is a specific goal to kill something. I remember that on higher difficulties you are sometimes required to eliminate certain enemies, but unless that's a specific objective then you don't have to kill anything.
There are a few tricks to get past guards without killing them. If you can sneak up behind them you can knock them out with your blackjack, and then hide their unconscious bodies somewhere. They won't wake up unless another guard finds them.
If you prefer a less violent route, you can always look for another path to your goal (the levels are very open-ended and there are lots of ways to get where you're going), or you can try and distract the guard with some sort of disturbance so he goes and checks it out. You can do this by throwing objects or using noisemaker arrows (if you have any). You could even let the guard catch a glimpse of you so he starts searching, then sneak around him. Also, if it's dark enough you can sneak right under a guard's nose. If there are torches nearby you can put them out with water arrows, then sneak right past the guard without him being able to see you. You'll have to be quiet, though, so if the guard is standing on a metal or marble floor, you might want to shoot a moss arrow at the floor so your footsteps will be muffled. If it's a wooden or stone floor you can sneak past without moss, just make sure you're moving slowly enough. I tend to sneak while crouched, and when I'm VERY close to a guard I might also switch to a walk while crouched. Running while crouched is usually quiet enough for most purposes though. That's just my personal style... other players stay standing and either walk or creep when they need to be quiet.
As for the map, it's certainly unusual, but you'll get used to it. Garrett only knows the basic layout of the places he's going, so you have to do a lot of navigation yourself. The map will tell you which general area or room you're in, which helps a lot, so be sure to check it if you're ever unsure of where you are. But yeah, this means that things like the arrow cache are actually a challenge to find... there's no "quest arrow" pointing you right to it. But that makes it all the more satisfying when you do find it.
The game takes some getting used to, but it's a really great game, so keep with it!