iTunes tends to have a weird way of creating their playlists when you have shuffle turned on. It doesn't really give you a good variety. It kind of favors the things that you listen to most and the things you've rated the highest.

If you want to listen to a broader variety of your collection, I'd suggest you create some nested playlists. Here's a couple of sites (link, and link) that have some good suggestions for this.

NaS, for some reason. I only have one album.

Favoring the things you've rated the highest doesn't seem weird to me at all.

People actually use the rating function? I figured if it was on my iPod, it meant I liked it.

I'm with BitterOldPunk. I don't rate anything because it's all stuff I like. The thought of going through my library and rating everything makes my head hurt...I tried to rate stuff when I had my first mp3 player but I could never keep up.

I also tend to do much better using my shuffle than I did when I had a 60g player. On the shuffle I keep it to about 100 songs and I constantly update it so it's actually stuff I'm listening to.

My old 60g (now a paperweight - was not an apple product) just offered too many choices for me.

I know this makes me a consumer whore but I love that Apple has made it so everyone can feel like their ipod containing their music is the BEST THING EVAR.

Right now on my ipod you can go from:
Guns 'N Roses - Paradise City --> Hanson - Mmmbop --> House of Pain - Jump Around --> The Jacksons - State of Shock.

That's awesome. I don't care what anyone says. haha.

I've reverted to taking my ipod to bed with me and listening unitl I fall asleep. Haven't done this since the early ninties with my sleep tape with headphones. Downside - battery burn if I don't shut it off before I crash. I also don't rate, pretty much shuffle, I think I have about 70 songs. But then I start with one to go to bed to and take it from there.

Look in Settings (or whatever) to see if the Shuffle function has a Seed modifier for the Random function. This can affect how often songs that are similar to favorited or most-played songs are seeded into the mix.

I have seen similar controls on a number of newer media players. The names may be different but the idea is the same. The default setting is often a moderate seeding.