Hi Rich,
I'm always playing with ideas for building more workshop space.
The best option is always build onto something existing like a lean-to or cover an area between two existing buildings. failing that building a frame similar to drywall and bolting frames together to make up the building you want, fix some battens on the top cover with marine ply and then felt the roof. The walls can then be covered with marine ply or boards. An alternative could be to use scaffold poles and like you suggested stretch plastic sheeting over it or drill and bolt corrugated iron sheets to it.
a concrete base is always a good start however paving slabs make for a good solid floor if laid properly. A wood floor can be constructed by suspending heavy battens or ideally old railway sleepers across flag pavers and then a boarded floor on top. you have the added advantage of having cheap lumber and materials in the US than we have in the UK big companies have swallowed up the small independents and set prices which don't reflect the average income over here. Don't get me started on European legislation - I voted out. You have 4th July and we have now got the 23rd June.
Best of luck, if you like any of my ideas then give me a shout and i may be able to help further. you might want to check with your neighbours if firstly they mind and secondly what the local regs are with regards building a non permanent building (that is basically a garden shed in the UK which does not require planning consent provided it is away from the boundary less than 300 square feet area and less than 12 feet in height - something like that anyways. Not a solid brick structure etc.

Shipping containers are cheap and ready built, old trailer van bodies are another. I personally want a 20ft container which i would clad the outside in larch lats to make it look natural and blend in to the garden - Big problem i have is 5ft 2" tall, pink, yellow on top and shrikes, repeating the same message over and over - your not having that in my garden, oh and female.

Two things you will need to consider, the local building regulations and does it require to be storm proof. I have heard you get monster storms and whirly winds in the US.