What are they? It varies from person to person of course. But much of the criteria must overlap because selection methods don't splinter much, fully random is highly popular.
Here's several criteria that might mean a nothing, a little, or a lot to you.
1. Multiple apparent viable strategies
2. Interactivity
2a. A rock-paper-scissors relationship involved in the strategies on the board
3. Low variance
4. Variance (usually in a kitchen table concept with players of varying skill)
5. Unique from other kingdoms you've played, at all.
6. The degree of uniqueness from other kingdoms you've played.
7. Has your favorite cards (this isn't the same for everyone, and even favorites tend to get overridden in favor of uniqueness.)
The most popular method, to my knowledge, is full random, and has been for a long time. It's intended to maximize 5 and 6, which for many people is important. Tinkering to improve the others endangers 5 and 5.
This thread isn't really about anything but 5 and 6, to be honest. There is such a massive amount of variety in Dominion to start with, you could probably trim it with very limited damage to 5. But any such change would be very controversial, particularly if a favorite kind of board is removed for the sake of perceived variety. If there are too many Jack boards, so one person argues that cutting Jack's probability to half improves the magnitude of uniqueness between games, but the other players who enjoy Jack games have a right to cry bloody murder.
So why did I make a thread about a change that can't happen? I think there is a very narrow set of changes to full random people could agree on - ones that treat TOTALLY identical kingdoms as if they were one kingdom. 5 is important, no one wants to play the same kingdom twice.
By an identical kingdom, I mean ones that contains X unbuyable, ungainable, not-even-feeling-blackmailed-by-its-presence, cards.
Hold the flamethrowers, there is NO card in dominion that is unbuyable in every kingdom it appears in. However, there are several weak cards or board combinations that can algorithmically be determined to make a weak card "obsolete" - reasonably skilled players will ignore the card, every time.
There's also the case when one strong card makes everything else in the kingdom obselete. There's several Jack only boards, and Jack-assisted-by-X boards. It's harder to build an algorithm for these cases, but maybe the brightest could eliminate the simplest cases where the lack of a village causes the board to be "pick the best terminals to go with your money". In such a board, Fortune Teller/9 terminals is not unique from Woodcutter/9 terminals one of those terminals will be a Vault or Merchant ship or Rabble, and the value of an action point will render the weak terminal Silvers an unbuyable part of the kingdom in both cases.
An example of the sort of rules you could add to an improved random algorithm is to define Scout as a blank card whenever every kingdom VP card, Ambassador, Tournament, Wishing Well, Swindler, Baron, Hoard, Menagerie, Hunting Party, Horn of Penty, and Crossroads are all missing. Counting House may happen to be a dead card some of the same kingdoms. Thus, the 9 card kingdom of x1, x2, ... x9, Scout or Counting House, can be considered one unique kingdom.