Perks are not random, they are based on the type of unit and also on previous perks taken (some parks are "repeated", so you can take them at different levels, but if you take one early on, you will be offered another perk instead).
I don't know if there is any perk list online, but here are a few things worth considering:
-Segmented movement is one of the most valuable perks in the game, it means that you will be able to perform hit & run attacks (and not clog up the front rank), and it also allows you to move near enemy units without any extra movement cost.
-For flyers, protection from shooting is a must.
-Terrain specific perks are usually not worth it, with the exception of forest bonuses (forests are common), bonuses for movement over water (water is not nice to stand in if you get attacked) or range bonus due to standing on a hill (for archers).
-When it comes to magic, go for healing spells first when possible. Weaker spells usually gives you more uses, but you will have enough spells later on for them to become totally redundant anyway, so go for the higher power ones.
-Armor piercing is very useful to have on at least a handful of your units.
Fnord- Warhammer Mark of Chaos = totally, criminally underrated game! I spent many, many hours on that one
Mark of chaos was flawed, I won't deny that, but it was fun, and yes, as you said, criminally underrated.