For standing at a lathe, you can just build a duck board to get your feet off the floor, then cover that in something a bit softer such as the Halfords workshop suggested by lankytank. Its the route I went down and means working at the lathe is comfortable whilst the rest of the floor is easy to sweep and doesn't get swarf stuck in it. The duckboard can be hidden under the lathe when not in use, or moved over to the milling machine.
Depending on the size of your brick pillars inside the garage, I'd suggest building framework that finishes flush with the inside faces, filling the cavity with insulation, then paneling the whole wall in 3/4" thick OSB. That would allow you to put shelves up just about anywhere, will take a coat of white paint easily enough and is pretty resistant to the usual workshop wear and tear. Might not be the prettiest surface I agree, but workshops generally have to maximise wall space so you see very little of it anyway.
If the planned life length of my workshop had been greater than it was, that would have been the route I went down.
Good luck, its a lot of fun!
Steve