I have a 30x40x12 and built a mezzanine across the back 10'x30' with rooms below. After some comments on here I was worried I'd taken up too much floor space but now that I have it framed up, I'm real happy. In addition to the extra 300sq ft I gained, I realized I had gained quite a bit of additional wall space for tools and benches in the new rooms.
I'm a tool guy so this works for me, I have a lot of stationary tools I need to place. If you're a car guy or want more open space, this may not work. That and its a lot of work, but you asked for ideas.
The mezzanine was key to my overall plan for organization. Everything frequently used will be downstairs inside a cabinet or tool chest. Everything I don't use that often will go up on the enclosed mez.