Greninja is probably one of the most popular non-Shay decks.
There's a few lower tier decks also, like Raichu/Bats, Magnazone/Raiku, which are very fun, but generally not considered quite as competitive as some other decks.
What are you two looking to do with the game? Play for fun at league? Play semi-competitively at local tournaments? Play competitively and try to make Worlds? Depending on your goals the answers may be a little different.