I definitely think we're getting better. When I got SM64, it was my first video game, and it took me about 3.5 years to get all 120 Stars (and a few weeks just to figure out how to get the first one). When I got SM64DS, it took me about a month and a half to get all 150 Stars, and I probably could've done it even sooner if I hadn't gotten Kirby & the Amazing Mirror and The Thousand-Year Door at the same time.
The only Mario games I'd complain about being too easy are the Advance games, which are made way too easy (except for Advance 3, I really liked the Secret levels).