Thanks for the input.
hmm, do you really need every new piece of "Terrain" to be completely random?
Because the terrain object is just a small tile in a much larger ("infinite") terrain system, yes. Each terrain piece should line up with the next to create a "seamless" environment.
If not, you can create a set of pre computed heightmaps in a image program which you can then load a random set from.
This is a different scope than the project, but not a bad solution for a different game. However, for me, this will not work.
In regards to your question, have you thought about generating a heightmap texture via shader code?
No, I have little experience with shader code, and might be something I can investigate later. I am not sure this even would work with my solution ( I dont know how to do that with shaders). The performance is only an issue because currently everything is on the main thread. I need some architecture level solutions related to Unity on how to address this. Something technical would be great, but a high level overview might push me in the right direction.