Generally it seems to be perferable (mehudar) to use an oil based candle for mitzvot. Why doesn't anyone use an oil based candle for havdalah?
Mishna Berura 298:5 and Beer Hataiv 298:2 mention in the name of the Sefer HaKavonos and the Magen Avraham in the name of the Kavanos HaArizal that it is preferable to use a beeswax candle for Havdala.
As you can see in the Halacha the candle is supposed to be an Avuka - which is more than one wick. This also makes it more practical to use a candle over oil.