Some thoughts:
Different parts of the country have different ideas about what a "small" bale is. Around here it's about 16x18x36 inches and weighs about 50 lbs. Each bale is 6 cubic feet, 1500 of them are 9,000 cubic feet, stacked 10' high that's 900 square feet, or a 30x30 area.
At 50 lbs each, 1500 bales is 75,000 lbs or 37.5 tons. If you had a loft rated at 40 lbs/sf you'd need a loft of 1875 sf, or 30x60. Conversely, to stack them 10' high your loft would have to be able to hold 80 lbs/sf. That's a lot to carry up to a loft.
When you're paying to have hay stored part of what you're paying for is the risk of spoilage. Even stacked on pallets and with plastic sheeting below the bottom layer of bales will usually get moldy for me.
The cheapest way to store hay is under a tarp, but I haven't had good luck with that, condensation forms under the tarp and drips on the hay.
The comment about wood shavings reminds me of an interesting technique I read of somewhere that stuck with me as a clever method. The author counted up his hay and shavings purchases for the year, and found that he bought one bag of shavings for every four bales of hay. At the start of hay season he bought a truckload of bags of wood shavings (at a truckload price) with a year's supply. He laid the bags out on the ground, and stacked four bales of hay on each bag of shavings. The bags kept the bales off the ground and dry. As the hay was used the shavings were exposed, at exactly the rate they were needed.