first there's the question, WCA or non WCA?
If it's WCA, you want a puzzle that's not like your usual 3x3, but also not looking like a regular cube because probably most of the people has 3x3, 4x4 and above and they are used to the puzzle, Square-1 and Megaminxs, Pyraminxs and lastly Skewb are fun If you never solve one. but there are lots of fun puzzles outside of the WCA categories too.
for non WCA, I suggest a mastermorphinx, they are pretty cheap.