I live in Illinois, so my building codes may differ from yours.
Currently, my water heater is located next to my furnace. This makes it easy to supply gas to it. I already had a 1" pipe from the meter drop down between the two appliances. It was easy enough to shot off 1/2" pipe to both appliances. Also, where your furnace is located you'll already have some kind of utility area set aside for it. It shouldn't be too hard to position one there. Otherwise, you'll have to dedicate some other utility area. You also have to keep in mind where the water will go if you develop a leak. An HVAC unit will have some kind of drain nearby to dump any water condensation from the AC. If your heater does leak, you can try to direct the water to that drain.
They both share a common vent and both feed through the fireplace chimney. The vent pipe is made of galvanized sheet metal. The size of your pipes should be determined by BTU load of your water heater and furnace.
I would not put the water heater outside. If I had a choice I would put it in the attic. When I lived in Louisiana, that's where my water heat and furnace were located. My attic would normally reach temperatures of 150degF during the summer. The water hear was generally set of 140degF. For 9 months of the year, I never used any gas (my stove was electric). That setup saved my a lot money. In my Illinois location the water heater is in the basement, where the air temp is usually about 70degF. So I end up spending a lot more on my gas bill.