By the way, I came up with the following "fluff explanation" for why teleport works the way it does. See how you like it:
----
Teleportation magic is inherently difficult. In order for it to work reliably, it requires a stable "magical energy field" at the end point of the teleport in order to "lock on" to. If such an energy field does not exist, it is necessary for the teleport magic to create one temporarily, but this makes the teleport take slightly longer (on the order of a second or two) which gives the defender another chance to resist it or use powers that will help them resist it (i.e. the saving throw, possibly modified with extra powers.)
The required energy field is produced by particles called "magitrons." Magitrons are continuously generated by any solid material. Unlike ordinary matter, magitrons are repelled by gravity rather than attracted, so they tend to fly upward. Additionally, magitrons have a very short half-life, so most of them only fly up a few feet before decaying. Thus, there is a magitron "field" that hovers over solid surfaces. This explains why you need a solid surface to teleport to.
Additionally, the rate of magitron production is temperature-dependent. It peaks out around 80 degrees Fahrenheit and goes down as the temperature diverges from that point, so surfaces below around 20 degrees (like very cold ice) or above around 140 degrees (like fire and lava) produce few if any magitrons - thus they have no magitron field above them and teleporting onto them is just like teleporting into air, as described above (i.e. hindering terrain). Similar effects occur for other types of hindering terrain hazards not based on temperature. For example, if there is a square that is hazardous because it has a rotating blade in the floor, the rapidly rotating blade creates "turbulence" in the magitron field, making it hard to get a good lock.
There is also one more fact to explain: why hindering terrain causes problems for teleportation, but temporary magical effects like walls of fire and cloud of daggers (that have similar effects to hindering terrain) do not. This theory can account for that explanation. To avoid unwanted interactions with other terrain or magical effects, sustained effect spells are designed to monitor their own influence on the magitron field and counteract it using the spells' own magical energy. Thus even a spell like Wall of Fire, despite increasing the local temperature, will leave the magitron field intact and thus not affect teleportation.