Agreed, the environment and theming were very well done. Some minor costuming was a bit off... Octavian was wearing britches at one point, and some other points of contention, but the 'feel' was there.
As for the story.. I can't understand why shows and movies can't use the real story, history is interesting enough in reality.
Some discrepancies off the top of my head.
As Ursus said... Octavian was far more savvy and cunning than portrayed.
The use of the term successor and emperor was thrown around too much. Octavian was heir not successor.
The chronology of events and details of the Senate actions were shaky. (ie sending out assassins after Caesar's family, the handling of the will, etc.)
The worst was the portrayal of Cicero as a Caesar lapdog. Once Caesar was dead Cicero openly supported the 'Republicans'.
The legions were not given any credit for their part in the drama and too much emphasis was placed on gladiators. Still I suppose the legionary role is yet to come.
There were other things that disturbed me here and there, but I waited too long to write this

Regardless I found the show entertaining and will watch next week. Still I'm pretty sure after watching tonight that HBO/BBC 'Rome' will be far more appealing.