Moderator: American AAdvantage, Travel Safety/Security & Texas, FlyerTalk Evangelist
Join Date: Sep 2006
Location: AUS / GRK
Programs: AA, HHonors, Hertz
Posts: 13,485
Agree on South Yarra, for Hertz at least. It isn't an enormous location, but they do tend to have access to more vehicles, so more options for an upgrade. If you're staying downtown (near Flinders Station), it is rather easy to get there via train or tram.
I'd definitely recommend calling ahead. They are nice guys, and I'm sure they can tell you what they would do for upgrades.