Just wanted to point out that XNA is fine for your purposes. Heck, isn't Mono.xna being developed as well for Linux support? Besides, it should just be a rendering engine for your purposes anyway. If your project is done right, you should be able to switch graphic rendering without modifying the gameplay at all.
I'm pretty sure you can embed an XNA 4.0 installer as well later on an installer of your own, so no worries about that. My only gripe at the moment regarding the display is that the aspect ratio is fixed.
Mono.xna has been dead for over two years now. There are a few open source engines that you can use as the basis for your game. There's the OpenSonic and the ProSonic engines, for one. Both are cross platform and support Sonic games well, with the former being able to support Sonic Heroes style gameplay as well as classic Sonic gameplay. I suppose the latter could too, with its scripting engine.
That being said, if the engine was written in C# (which it probably is if it is using XNA), then porting it to C++ wouldn't be too difficult. The hard part would be finding equivalents of the various pieces of XNA that are C/C++ and cross platform. That can't be done without knowing what pieces of XNA were used...