I've already commented on how not random my iPod is, but now it's getting weird.  I selected "Shuffle Songs" and this is what it did:

Song 4:  "I Am the Door" by Day of Fire (from the Day of Fire album)
Song 5: "Run" by Day of Fire (from the Cut and Move album)

I know, I know, you can adjust in iTunes how likely you are to hear a song by the same artist.  Mine's right in the middle.  And I know that sometimes it's gonna' randomly repeat songs by the same artist, but it still took me by surprise.