Ideally, what Dave said.
I rent a 17 x 27 - and as far as work on car space goes, that's plenty.
Alot depends on how much else you have in there.
Ideally figure room to open the doors. If you get a lift, then you can't cheat by parking closer to one side or the other.
If you're going to use a floor jack, plan on room behind the car so you can use it with the garage door shut.
Personally I like the toolbox with wrenches close to the engine bay, and a work surface nearby as well.
Will there be shelving? A place to hang lights.
Compressor?
Washsink?
Toilet?
Other equipment? A parts cleaner is nice!
I store a fair amount in mine as well. Extra parts, competition tires. etc. etc.