I don't really work with Python so can't help much but:
For Linux, assuming you are able to create something that is self contained (So, no install instructions needed) then I would just zip that instead of going through the effort of making a proper .deb file.
Worst case: make a START_GAME.sh file or similar that looks if everything is installed and if not tries to use the package manager from python to install it before launching the game. Ideally make it known to the player that it will do this and give them a way to bail out in case they want to install it in some other way.
I don't know good workarounds for Windows though as it has been very long since I last used that and I have no idea what is and is not available for that.