West of the Moon, East of the Sun by KnifeEdge has Buffy take a stroll through Spike's past, to better understand his relationships and how he was shaped by them. She comes across the gruesome exploits of Angelus and William the Bloody on the way. It's in the third part though...the story spans three parts and 76 chapters.
Book Two of Forward to Time Past by Unbridled Brunette follows Spike's career with the Whirlwind from the time of his turning until he meets Buffy.
Wolffan200's ongoing Spike epic "Twists and Turns" have detailed and delicious interaction between Angelus and William. It's an AU where William is a demon hunter before he is turned and Angelus was never cursed with a soul.
But seriously, the best stories where their relationship is explored are all Spangel. Not all of them have them being all forget-Buffy-vamp-love-forever. The ones I love are ones where they're each insanely jealous of the other's being with Buffy and under all the violent history there's a deeply buried caring for each other that they have no idea how to express. Other than violent sex.
Have you watched Angel? Because you're basically looking for AtS Season 5 episode 8 "Destiny", where they beat the stuffing out of each other, complete with flashbacks.