I used Pandora a lot when I was a teenager, and experimented a bit. If you were listening the same time I was, the size of the library probably wasn't the primary issue.
Presumably their recommendation algorithm and the Music Genome Project tagging allowed them to, given a set of tags, find similarly tagged songs. This worked really well. It's how they used it and how they picked what track to play next that caused issues.
First, thumbs up. As far as I could tell, at the time Pandora would strongly prefer to play a track you'd thumbsed up on a station over anything else, as long as it was available to play, which mainly just required it to not have played to you in the last two hours. So if you used thumbs up the normal way, a well-used station would eventually turn into a loop of things you'd already heard.
Second, the way they used the algorithm - it seemed to me like they only or mostly used the station seeds as the input, there was no blending going on, and if thumbs ups impacted it, well, they had their own problems. That is, if you had a station with two seeds, it played some songs close to one seed, then it switched to the other seed and played some songs close to the other seed. Skipping would usually bump you to a different seed.
To get around all this and get a variety of new material, I created a station with a lot of seeds - 25 to 50 or more - and never thumbsed up anything on it.