I want something that can warm it up fairly quickly. I may only be out there an hour or 2, but when I decide to work on a project I don't want to wait an hour or 2 for it to heat up. Right now I have a cheap portable oil heater and it takes a long time. Would prefer something cheap if possible.
Look into the Mr Heater brand of propane heaters. They make a round one that attaches on top of a standard propane tank like your bbq grill probably uses.
They make a full range of heaters up to giant ones that contractors use, but I'm only familiar with the round tank mounted ones.
I've been in house boats that use the single round burner mounted on a propane tank setup and they get unbearably hot after running the heater for a few minutes every so often.
I like my ceramic space heater; it warms up the otherwise unheated spot in my basement quickly. If you choose one, make sure it has an automatic shutoff when tipped over, or for over-temperature conditions. They start out pretty cheap at around $20; more money gets you nicer styling or features like a remote control.
If you want an shop heater that works really quickly, look into a torpedo (aka Salamander) type heater. They are a forced air heater so it will quickly warm any space you use it in. They're commonly used on construction sites, I've been on many jobs in the dead of winter where the heat isn't running yet but a salamander heater is keeping a large uninsulated inside space warm when it's 20F outside.