I have just experienced this bug on my realm.
Game froze with the Building Terrain message while going from nether to overworld. I wasn't doing anything unusual as I went through the portal (wasn't eating or similar)
When I logged back in I was in the overworld, suffocating in stone at the same co-ords I had been in when exiting the nether. (same as OP) There were no other players online. Similarly - since the latest update we have also been experiencing suffocation damage when going through portals (nether to overworld) where we have been spawning a few blocks under the portal when arriving in the overworld.
I'm having the same issue on my realm. Not all portals are effected and cause damage. The water breathing bubbles appear very briefly as I transition through the portal from the nether to the overworld (as if I'm under water) and I take from half a heart to a full heart of damage. This is affecting approx half of the portals on my realm.
This happens on my realm too but not only in completely new chunks. We get the chunks loading/you may experience performance issues message in well used zones (overworld) We've not tested this in the end (not wanting to fall into the void because of the chunk loading issue) We have pretty beefy computers and good internet speeds. I even invested in a 10 player realm to see if that would give better performance than the 2 player realm (uploading our long term world to that new realm) It made zero difference.