I have a propane "garage" heater that I got from Northern Tool. It's 45,000 BTU and heats my uninsulated 25x26 garage from zero degrees to the 50's in about 20-30 minutes.
Its a vent-less design so you don't need to put a hole through the roof or wall and has an oxygen depletion sensor to shut it down it the CO2 levels build up.
I purchased it at the end of the heating season for around $200 not sure what they go for now but Northern Tool always has them.