Batches can't be queuing (querying for records and getting the query locator ready and whatever else is in there start portion) at the same time.
So in your example, the first request in will queue, and then start it's execute method, and the the next batch in line will start its start method.
They can all be processing concurrently, but only one start method can go at a time.
They become an async job with a status. You can see apex jobs and their start time and status in the setup part of salesforce.
And yes, the first 5 in will run, everyone else will get a limits error.