i just tried this with some variations:
1 - if nothing is selected and i click the Play command button (in the bottom menu bar), the first track played is random
2 - if i do have a track selected, it will the selected track first and then random
3 - if i right click a track, and select Play Now it will the selected track first and then random
4 - if i right click a playlist and select Play Now, it always plays the first track and then random
5 - if i click the play button in the player control panel, it plays the song in the panel first and then random
There are also settings that affect the random behavour eg. shuffle higher rated tracks first, same/different artist bias. If same/different artist is selected, it will use the artist in player control panel for the seed artist so that will also affect which track you hear first.
For 4 I will amend. For 2,3, i am not sure that should be changed - i could imagine someone wanting to select a specific song to hear first. And 5, i think is the correct behaviour - just click the next track button instead and it will start at a random track.
Which one of these were you using?