Hmm, there's a few things I didn't see in your list we can try:

1) Try running Sins of a Solar Empire Rebellion.exe directly from your install directory (you can find this by right-clicking on the game in your Steam Library, selecting Properties and then Browse Game Folder).

2) If that doesn't work, you can try disabling the in-game Steam Community overlay.  In Steam, select Steam from the top menu, then Settings. Click in the In-Game tab and uncheck Enable Steam Community In-Game.  Please note this is a global setting, so you'll need to re-enable this for other games if you want to use the feature.

3) If that doesn't work, try running Sins of a Solar Empire Rebellion Dev.exe instead. That won't let you play multiplayer online with other folks, but it may let you run the game.  Plus it'll start in a window, which may help.

If you open up rebellion.user.setting in My Documents\My Games\Ironclad Games\Sins of a Solar Empire Rebellion\Setting you can modify the various graphics settings.  It's all pretty self explanatory, but for the various texture quality settings, you'll want to knock them all down to 1 to start with. 

Almost sounds like the file permissions on the C:\Users\%USERNAME%\My Documents\My Games folder aren't letting the game create its subdirectory.

Thanks Yarlen for the files.
I made the directory as follows:  

C:\Users\[name]\Documents\My Games\IronClad Games\Sins of a Solar Empire Rebellion\Setting 
and extracted the three files into Setting, however this STILL hasn't managed to get the game running.
I also changed the resolution to 1600 x 900 and all textures to 1.
I think I'm destined not to play this haha. 

Thank you anyway.

I'm having this exact same problem. Steam does not like Sins very much apparently.