Livy is fun. Herodotus has his moments with the occasional side story.
And for beautiful but biased prose, one simply cannot improve upon Gibbon (yeah, yeah, I know. bad guy).
Ditto to Josephus. Also check out CK Barrett's New Testament Background: Documents
It wouldn't hurt to brush up on some Philo. Mind you, horrible, horrible theology but Alexandria, Egypt was the intellectual center of the ancient world.