It happens, that is because terraforming improvements have quality level corresponding to to quality of unconverted tile and if there is no tile they can convert that improvement is effectively wasted. I can't give you exact details since I never look at those numbers closely and only thing I can recommend is to use terraforming in order you get them in tech tree to minimalise this effect. This is actually a problem on big planets like 15+, I don't remember having it on smaller ones.

its not about planet size but quality of tiles, you will be able to use more advanced terraforming techs

it is pretty annoying when cycling through planets and looking for terraforming tiles, but some of them are both available and unusable.  It would be nice (from a QoL and UI standpoint) if a planet with no available tiles for a terraform, would at least grey out those improvements.

Random.

Quoting Unknown_Hero,

reply 8

If the game is well designed, the random range can work in any case.  

It could have been better solved/explained in game but considering all this is non issue and you are wasting time.