Assuming you don't drive long vehicles, my vote goes for wide and shallow.
If you have a narrow and deep garage, you only get the one back wall for work space -- have to keep the side walls clear so you have room to open car doors and climb out. But with a wide and shallow space, you can use BOTH side walls for workbenches, tool chests, utility sink, etc. Basically, nearly double the linear space.
But as others have noted, if you have/want a long vehicle you need another 5' depth in order to close the overhead door and work under the hood, so bear that in mind...