I think since everyone here is a cube designer, we have a somewhat skewed view of complexity compared to the average player, specifically because we are (mostly) building with existing pieces and including a lot of rares and complex cards compared to your average limited environment. A new player likes Gollum in a vacuum or in a precon surrounded by less exciting cards (and why wouldn't they, it's flavorful, he asks you a riddle!), but probably would not enjoy the game in aggregate if every card in their precon had that much text and complexity. But they're a new player, so it's unlikely that they would be able to articulate that unless they already have some tcg experience. For us, we're trying to think about that big picture aggregate experience instead of just thinking about cards on an individual level, so we're all a lot more cognizant of the cumulative effects of complexity, because most of us are not running Thraben Purebloods or whatever, we're running cards that excite us.
I also think there is a huge difference between a card like Gollum that uses it's complexity to tell a story vs something like Questing Beast which is not evocative at all and just feels like word vomit. Gollum is more grokable because it is representing something that a player would expect Gollum to do. (EDIT: this point got made for me while I was typing this lol)
I also think that, similar to what LadyMapi was saying, there is a difference between "lots of words" and "hard to understand". Gollum has a lot of words, but it's basically written in plain English in a way that someone with no Magic knowledge can understand. Compared to cards with very little text but that include things like "protection", or "the ring tempts you", or "venture into the dungeon", Gollum has more words, but is easier for a new player to read and get what's going on without help.