It has nothing to do with non-linear stories (for me at least), and it certainly has nothing to do with Batman Begins - though these are two good reasons for loving him.
The reason I love him most is simple: He gets amazing performances from his actors. He's an "actor's director". That's my #1 reason.
Memento - Guy Pearce's performance, the backwards storytelling, the music, Joey Pants, the ending... Everything here is subperb. Instant classic. Nolan said "You can do things different", and BAM! he did it.
Insomnia - My favorite Nolan film by far. Al Pacino, Robin Williams, Hilary Swank.... It's got great talent, a great story, the simple telling of the story. Easy camera shots, very simple, effective. Very moody. Nolan makes a movie dark even though the whole movie takes place in the day. That's talent.
Batman Begins - This is bias, since Batman is my childhood hero, but once again, one of my favorite movies, great storytelling. He made a Batman movie without it feeling like a Batman movie. It's a man's man movie, not for kids, but for adults. It's like a Batman movie disguised as the ultimate guy movie. "The Godfather" of superhero movies.
The Prestige - My least favorite Nolan film, but I still love it. Very confusing storytelling, very interwoven and frustrating on purpose... It does its job effectively. It's a masterwork of plot twists and surprises. Excellent climax and conclusion. The writing overall is well above most movies today.
