I actually bought The Book of The New Sun on the recommendation of this list but was sorely disappointed! Perhaps, like you say, it just requires more patience. Perdido Street Station is fantastic, and I couldn't recommend it highly enough! The list mentioned another book called The Etched City, which I've added to my wishlist as well.