Nether Portals briefly teleport the player to their starting location, but in the other dimension. If there is fire or lava at that location then the player takes fire damage after portal invulnerability has ended. This is accompanied by massive server lag / desync in MP and massive frame lag in SP. This is most likely caused by the anti-cheat (speed hacking) engine teleporting the player back to the original location.

e.g.
Overworld portal at (100,64,100)
Lava at (100, 64, 100) in nether

Overworld ==> Nether:
Fire damage (after portal invulnerability has ended)

Note:
In 1.9 pre-4 this issue was partly fixed by the adding of portal invulnerability. However this workaround is temporary for the 1.9 releaseat best as you still load the far-away chunks, catch fire and so on. The real underlying issue is the anti-speed hacking engine or whatever it is that produces those <PLAYER> moved too quickly messages being too trigger-happy.