I was thinking about getting luggage racks for mine (the overhead type that they have on trains etc) Put them high up on the wall for storing parts etc
Old filing cabinets make good toolboxes and ideal storage. Metal file cupboards are also great
Put in as much bench space as you can, you can never have too much. Kitchen units make good benches and are cheap second hand.
As Miniminx said, get a kettle in there, its nice to have tea on hand so you don't have to keep going in for it. (i'm lucky, my garage is off the kitchen)
Heating is nice, i have a 3 metre GCH radiator on my garage wall which makes a nice difference.
Paint the walls and ceiling white, it will make a massive difference, as will grey floor paint on the floors.
Lots of sockets as has been said already.
I do have loads of other ideas but can't think right now. Ill update when i think
Ben