The inner north of melb, from Flemington to the West to Northcote as far as Fairfield to the East is bike heaven. Flat. decent roads. interconnected bike paths if you get sick of roads and are happy for a slower commute.
Check out this map of the Capital City trail which loops from Fed Sq and back again via Richmond in the East, up through Abbotsford, then east/west along the Park St bike path, down back to Flemington, and then Southbank. The trail goes just north of royal pde, so close to Melb Uni. If you lived anywhere close to this path, you will have a car free commute via bike to the Uni (via north/south Canning St, or even Royal Parade on road bike path) .
http://www.bicyclenetwork.com.au/media/ ... %20map.pdf I think Fairfield is a little more affordable rent wise than some of the trendier inner noth suburbs. Its boring, but close to some of the action. And also close to Heidelberg.
Edit: Just noticed that the OP's gf doesn't work in Heidelberg. Woops.