I didn't mean that the beds are uncomfortable, but that the futons feel much like a mattress that happens to be on the floor. However, I prefer a firm mattress.

I would try IACE New York. Their LA branch has excellent service and great deals. They can also get you a rail pass and answer miscellaneous questions; they might even be able to book you a hotel known for soft mattresses, or call for you and ask.