Nice! I wish I had that space, but I am lucky to have what I got (my shop at home is 8 x 12 feet).
For flooring you could use the industrial linoleum tile squares, with the rubber/vinyl edging. The edging is important (you need edging, of some manner, no matter what). The tile comes in many colors, so you could color code work areas, and also "mark off" danger areas and such if you want. Plan out your workspaces and where they will go early, before you lay the floor, then use the tile (or if you go with something else, another method) to mark off the zones - for instance, if you have a large and dangerous machine room area, mark that off with caution stripes or something.
If you do robotics work or such, you might want to tile a section of the floor in an alternating checkerboard (black and white) pattern, so you have a "reference pattern" for motion and vision experimenting.
You also need a laser cutter, a rapid prototyping machine, and a CNC mill. 
In all seriousness, though, you may want to think about a few large "gorilla" racks for storage. These racks are pretty heavy duty, and easy to put together (you need a rubber mallet). Purchase a bunch of rubbermaid-type tubs (or the translucent kind with flap lids) in two or three sizes -all at once-, and store larger items or assemblies in the tubs. Be sure to label them all (oh - if you don't have one, get a label maker for your lab), except for the empty ones, of course. You need to buy them all at one time, so that you know you have extras on-hand that match what you currently have in use; sometimes you end up buying storage, then go back in a year for more, and you can't find the ones you bought previously to match in the same size/shape - so nothing fits.
Finally - you mentioned that you already had parts drawers; are they all the same kind? This is important too - I found on the reorganizing of my shop to just ditch some random parts drawers I had, and instead I bought a bunch of Stack-On drawers (and a bunch of extra dividers); I have found Stack-On drawers to be perfect for all my small parts, and everything matches well. You might think I'm crazy for all this "purchase a bunch so they match" business, but the fact is, keeping things regular in organization (and labeling -all- of the drawers) really helps you to find things.
Above your workbenches, if they are against a wall, you should put in shelving standards rails, brackets, and melamine shelving; such a system will allow you some adjustment as time goes by, while having a sturdy shelving system (anchor the rails to the studs). You can use these for test equipment, power supplies, extra storage, as well as a space for books.
If you don't already have one set up for your house, think about setting up a central file server(s) for "stuff"; I ended up building a small "server closet" in my shop, which is networked to the rest of the house. I store on the server a ton of stuff; one section is reference for electronics and robotics - so I have a bunch of spec sheet PDFs, tutorials, projects, pictures, etc. I can access these from my office or my shop (well, I still haven't built my shop computer, but soon). So, if I am browsing around looking for something, and it is interesting to electronics work, I can put it on the file server, then look at it later as needed in my shop (that's the theory, at least). The reverse is true as well; if I am working on a project in my shop, I can reference it later in my office as needed - I can also reference it from any computer in the house on the network (and with wireless, on my Android phone, and netbook, too).
Finally, make sure you have some kind of air conditioning system. My shop is currently somewhat miserable for a portion of the year (like right now) because I don't have any real A/C in it (I have a portable swamp cooler, but that's about it). I plan on fixing this during the winter, if I can get it done (I am thinking about a mini-split A/C system).
Oh - one more thing - something I wish I had room for, and you most certainly do - is a largish central work table/bench; you could even put it on lockable casters for positioning it as needed. I should also mention that you might want to think about a set of double doors to the outside, with a concrete pad and a transition ramp or something; this will help you move in/out larger projects and tools...
