I have a 34x22 shop in a seperate building. It has natural gas, so a ceiling mounted furnace does a good job. I modified an old style manual thermostat to allow it to be set to about 4C (38F). Most thermostats don't allow a setting below about 15C (50F). I leave it there most of the time. When I go into the shop I turn it up and it is comfortable in less than 30 minutes. Keeping everything above freezing avoids most condensation issues and machine rust (our climate is dry anyway), and keeps the tools and floor comfortable enough to use.
The current shop is divided into two by a wall, with 3.5" of insulation in the insulated half. I'm in the process of upgrading the unheated portion to 6" of insulation (12" in the ceiling) so I can remove the dividing wall and use the full shop. the plan for next year is to upgrade the other half to 6" of insulation as well.
I didn't build the shop. We moved here about 18 months ago. If it was up to me, I would have used a heated floor. the shops I've seen with heated floors are very comfortable to work in.