In your case, go with a used hybrid-style bike.
Something light, with ~28inch tires you can pick the best tread as is applicable. MTB bikes will ultimately be "slow" for a commuter, you are primarily going to be on city-streets so don't bother with an MTB-design, too much of your energy is transferred or absorbed by the wheels, shocks, tread, etc.
Street bikes make up the other extreme -- fastest and lightest; nimblest, but equally less comfy and ultimately less fun. After all if it's not fun to commute on the bike, what is the point? I don't feel that shocks are needed, at-most a comfortable seat in terms of things that slow the bike down in exchange for comfort.
I ride a hybrid that is tig-welded aluminum, 18 speed, looks like a cruiser but has the upright-stance that, well ... it meets the middle between a comfortable, practical and efficient stance. I'm up high on the bike -- I look down the rooftops of cars - this particular bike is out of your price range but if you watch whatever your euro-equivalent of Craigslist is closely, you'll find an awesome hybrid that is light, nimble, safe, like-new and as fast or faster than most road bikes.
I don't want to sound biased or like I'm plugging a brand but I ride a 2011 Townie 2200d; it's a rare design and the company doesn't build this design, the bike or an 18-speed gear set anymore (Shimano-custom - 2 up front, 6 rear w/ an extra low 1st gear) today they make 7 speeds, which can be had new in your range.
They are extremely popular commuter bikes in California mainly for being fun, safe, light & fast -- the winning combo for getting from point a to b then back.
"fixies are less likely to get stolen," is false. Fixies are in high demand due to the reasons you cited that you might want one. They are a bit cheaper since there are no derailleurs ... but a bike thief can turn a fixie into cash same-day making them just as desirable as a MTB, hybrid, beach, or road bike of equivalent value. Sometimes more so, due to the demand. What good is a stolen $5000 bike unless you have someone ready to buy it?
The biggest mistake I see with bike owners is that the quality of the lock and bike are often in inverse-proportion. Once you settle on a bike - choose a quality u-lock and use it always. Just to run into a store? Those times when you think "I can leave it unlocked, this will only take a moment + I'll be able to see it the whole time." That's when you should at least lock the bike to itself. No opportunist is going to jump my townie in such fashion; they'd have to carry it away + have a truck or something ready to throw it in, otherwise the theft would be entirely impractical. If everyone took the same extra time I do with security; far less bikes would get clipped.
Also take note that I've had knee & ankle replacement in my right leg - the stance, feel and ride to that bike is perfect for my needs. If I can ride with dexterity and speed (and I am not in awesome shape, not even close) then anyone can - great design goes especially far when it comes to commuter bikes.
Go with gears! At least 3. Even if 99% of your ride is on a flat, it's that errant steep driveway or uncommon hill that will leave you hating life if you cannot shift.