Recording and playing back input events, at least, shouldn't be that expensive unless you're emulating the entire stack up to the application. If the logic is written in some portable manner (Xamarin [1], etc.) you could just re-execute on the server with the same logic as the client. It requires a fair amount of discipline to keep everything deterministic, too. The real difficulty would be identifying the AI players from the humans; you'd basically have to recreate re-captcha's humanity checkbox, and that's still not a guarantee.
Or, identify that your business need is just to provide 'some' sort of ranking and compare the user against their Facebook/G+/Twitter friends, who are probably less likely to cheat.
Your second point is the important one for most games I think. Global leaderboards on a popular game are meaningless for the vast majority of players (do you care that you are in position 324,675?) and almost all of the implementations I've seen have been hacked. As this thread has discussed it's hard to protect false data from getting in the leaderboard.
Limiting leaderboards to friends both gives relevant context for fun competition and mostly eliminates the cheating problem by making it a social issue. I know my friends wouldn't be happy if we were all competing on a game and I cheated.
FWIW it's a fun domain space, partially these cool technical approaches(lock-step, dead-reckoning) and partially smart user interactions(how you decide to give users immediate feedback when you won't actually know until 100-800ms later).
Or, identify that your business need is just to provide 'some' sort of ranking and compare the user against their Facebook/G+/Twitter friends, who are probably less likely to cheat.
[1]: https://www.xamarin.com/