According to the city, since the garage is considered 'attached' because of the pergola structure, there is no restriction on how close it is to the house.
If we do not have it attached to the house, there is a 2' setback limit and the height cannot be more than 14' 6". However - there is a significant size restriction: 380 sq.ft. is the max I could go (it is currently 390 sq.ft.), and that would make our shed illegal. This is because our property has a maximum of 8% use of total sq.ft. for outbuildings (aka detached garage, shed, etc). 8% of the property is 380 sq.ft.. The shed is currently 6x8', and puts us well over.
Attached to the house, the limitations change from 2' setback to 4' setback, but because it is now part of the house, the max is 40% of the property for house including garage. The house is something like 1100 sq.ft., and I seem to recall 40% of the property being like 2500 sq.ft. - aka no restriction on how large the garage gets, along with the height max being no higher than the house (I think something like 17-18').
Boiling it all down:
Attached: no size limit, max height 18', but 4' setback
Detached: 380 sq.ft. limit (and tear down shed), max height 14' 6", but 2' setback.
At this rate it won't be until the weekend that I'll have time to do more Sketchup, but I'll definitely post up the other options then.
All this interest is encouraging, thanks guys!!