When I hear "cute, story-driven, mysteries and such" the first thing that comes to mind is Yuri Kuma Arashi. It's a short, bizarre show from last year that's a little hard to describe succinctly, but if you can put up with strangeness you might like it.
And even though it only fulfills two of your criteria (and has been described by the creators as deliberately, aggressively un-cute) I always recommend people who are new to anime check out Psycho-Pass. It's a mostly-straightforward sci-fi crime drama that I think is worth looking at if you're new to the medium because it gives a nice contrast with cutesier schoolgirl-centric fare and presents a spectrum of the kinds of anime that are out there. And it's not dissimilar to western movies and TV in a lot of ways, which makes it a nice stepping stone from American media into Japanese media. And, you know, it's really good.
And finally while I'm usually hesitant to recommend it to people who are new to anime it's going to get spoiled for you prerry quick if it hasn't been already, so you should probably try Puella Magi Madoka Magica. It's a short series, technically fulfills all of your criteria, and is probably the most influential anime from the last few years. I won't say too much in a futile attempt to avoid spoilers, but if you like it you'll love it.