I suspect none of those things you found were thought to be cheesy by their designers, so I suppose what you’re looking for is something only you will know when you see it.
There’s not a whole lot you can do with these family tree infographics. Making them functional pretty much requires a whole series of boxes in an expanding geometric sequence. You can put patterns behind them or make them look like branches of a tree or treat them as straight-forward boxes and lines. In the end, though, the boxes still need to dominate since they hold the ancestors’ names that form the basis of the whole thing.
I assume you’ve done a Google image search, but didn’t like what you found. Judging from your question, I’m guessing you’re not a designer yourself (otherwise, you wouldn’t be looking for a template). Even so, designing something personal for someone, where the main requirement is coming up with what the client personally likes is a tough problem. It’s not easy reading people’s minds and catering to their subjective tastes. Have you tried just designing it yourself?