Elder Scrolls 1-Arena
Elder Scrolls 2-Daggerfall
Elder Scrolls 3-Morrowind
Elder Scrolls 4-Oblivion
Elder Scrolls 5-Skyrim

So my question is where do Redguard and Battlespire fit in.

And what were their stories? From what I gather Battlespire involved Mehrunes and the Daedric Crescent and you had to rescue your girl from the Battlespire. And Redguard I have no idea what thats about

They're both spin-offs, so if you're discussing the core series you wouldn't even include them (or the Elder Scrolls Travels games, like Shadowkey). If you are talking about in-game chronology Redguard comes first, followed by Battlespire, and then the core series. In terms of game releases, Battlespire was released after Daggerfall, then came Redguard, and then Morrowind.

Redguard is about a Redguard named Cyrus as he searches for his sister, all the while getting caught up in the politics of Stros M'Kai as the Empire is taking over the area. He's also the biggest badass of the series.

Chronologically?

Elder Scrolls Legend-Redguard
Elder Scrolls 1-Arena/Elder Scrolls Adventure-Battlespire
Elder Scrolls 2-Daggerfall
Elder Scrolls 3-Morrowind
Elder Scrolls 4-Oblivion
Elder Scrolls 5-Skyrim

Redguard is a prequel to all and Battlespire takes place during the Imperial Simulacrum.

There once was hardy young lad of the sea, a Redguard of courage and honor was he...

I also suggest reading the comic that act as a prequel of Redguard as well. See Cyrus' awesomeness in action!

http://www.imperial-library.info/content/cover-0