I'll echo others and say Deadpool then Maiden. Deadpool just has crazy energy to it - weirdly goofy and hilarious. Modes can run deep enough while still being accessible for newer players, but if you're a stud you might blow it up pretty quickly. Shots are relatively unique to recent Sterns (I know the cross-playfield shot is similar to original Avengers).
Maiden can really yield some long, flowy ball times, but can also kick you in the teeth. I found it a little less accessible for my current skill level, in that I hit a certain wall where I couldn't get a ton further without getting frustrated. That said, the composition of the modes really required me to work on specific skills that I feel have made me better on other machines now.
I rented both for a month and was thinking of buying both. Bought Deadpool and then didn't feel like I needed Maiden anymore, but they do complement each other well.