How to have random counter placement at game setup

That fact alone could make this an easy task.

Dice version:

You can roll a die to determine the direction compared to the starting position of the player.
Then roll another die to determine the distance.

To make it fair. Simply have a list of distances to choose from.

If you rolled a direction or distance before, simply select the next one in the list.

For example in regards to the direction:
A player rolled 5 2 3 3 2 2.
But the directions order would be 5 2 3 4 6 1.
Then roll for a distance. The list could be: 1=8, 2=10, 3=12, 4=15, 5=18 and 6=24.

I don't know what distances you have in mind. But to make sure it has some fairness, there should be a list for every player.

If anything is in the way. Simply have that spot move away by 1, and another move closer by 1. Rinse and repear I guess.

To add a little bit more randomness. You could even have the player being relocated. Perhaps even the same way.

To some locations, it would be closer, to other locations further away. No matter how the player is moved. The effect will be 100% fair to all of the players.

Cards version:
This is even better.
Simply have 1 stack have the direction and the other stack the distance.
Shuffle and combine.

would it make sense having an initial phase in which players take turns placing the counters?
You can swap the round order, so you go 1-2-3-4-4-3-2-1-1-2-3-4 or find other ways to balance the advantage of going first.
I don't know the rest of your game, there is a chance this can be a nice addition or it could make absolutely no sense thematically and be tedious.

Another option, that is used in several games (I don't recall how the principle is called) is that one player distributes the counters, and the other players choose their colours (it's usually done for 2 players, but would work with 4 if the person who distributes the counters chooses last).
This means that the person placing the counters will make effort to give everybody the same chances to win, as they will be the one left with the last choice!
Hope any of this helps,
Antonio

I would suggest some of what's been said above.

Players alternate, in reversing turn order (Player 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, etc), placing counters with conditions;

- May not place a counter within X hexes of your starting location
- May not place a counter within X hexes of the counter placed immediately before
- Must place counters within X hexes of Y landmark (if you have landmarks, such as fields, trees, rocks, etc).

Can you place multiple counters on a single hex? If so, is there a cap to the number of counters on a single hex?

Here's a silly idea:

The Good: Random, completely objective, relatively quick.
The Bad: Requires extra components (bag, blank tiles) – unless those components are already part of the game (in which case you're getting extra use out of them. Good deal!)
The Interesting: If you need (or want) to distribute additional resources (other than sheep), this is a good way to do it.

All that said: I also like the "landmarks" method.

If you want the counters to be truly random, you could roll two d20s and use their values as coordinates on the 20x20 grid to determine a single hex.

How do you balance between both methods? At 50% you're looking at re-rolling 50% of the time. That's already a bit excessive, no? But there is an alternative to dice: cards. A Deck of 36 cards with each one of the hexes as a readable number (1-1 to 6-6). As in your suggestion this will dramatically improve use-ability without any requiring of re-rolling.

It could even by a MINI-Deck (smaller cards just with the numbers).

But yeah, brilliant Lewis (@lewpuls)...

Yes, cards better, but cost a lot more than a pair of dice. Cost of manufacture is always important in commercial games.