Joss originally planned for Whistler (whom we saw in "Becoming") to appear to be a main character. When the actor's schedule didn't work out, he created Doyle.
Kate was originally going to have gone undercover as a prostitute, Become The Mask, and gotten addicted to cocaine—all before she was even introduced. It was decided that this might be a bit much.
The character of Jhiera, the demon in "She" was considered to become a recurring character. "The Ring" bringing up her demonic species (the Vigories of Oden Tal) was likely a reference to establish her as a part of the greater tapestry. But ultimately, this didn't happen.
Season Two
Kate was also supposed to have an important story arc in the second half of season 2, but Elisabeth Röhm got cast on Law & Order. She initially planned to do both shows but the constant flying back and forth drained her too much, so Kate disappears after "Epiphany". The Pylea arc was written to replace her planned storyline.
Season Three
Kate's arc would have eventually led to her becoming a full-fledged Hero Antagonist / Anti-Villain, opposing Angel and vampires in general as a result of her bitterness over her father's death (and Angel bringing her into awareness of the supernatural), rather than their moving reconciliation in "Epiphany". This would have led to her becoming Holtz's key disciple, having an uncomfortable father-daughter dynamic - as opposed to the semi-romantic, semi-familial overtones that Justine (who was created to absorb that part of Kate's arc in the greater narrative) had with Holtz. No word on whether Kate would have continued to serve a role from there or been written out like Justine was.
Season Four
According to Tim Minear, the original plan for season four was to have Cordelia be the Big Bad, culminating in her fighting Angel. Charisma Carpenter's pregnancy meant that the arc had to be reworked, and so they decided to write in the pregnancy and that whatever Cordelia was carrying was going to be the true Big Bad. They didn't have a good grasp of what the baby was going to be though, other than being male and evil. This later turned into Jasmine when they decided they wanted something different than just another Generic Doomsday Villain
Even after the Jasmine/Cordelia arc was heavily reworked after Carpenter's pregnancy, the creators planned for Cordelia to wake up from her coma and kill Jasmine at the end of the arc. Carpenter was, however, still heavily pregnant and unable to work the hours required, and so she remained in a coma. This also raises the question of whether Cordelia still would have been written out in season 5 if she had woken up earlier.
There was talk of Doyle coming back in Season Three or Four as a villain. Glenn Quinn's death quashed this. In season five, however, antagonist Lindsey pretends to be Doyle, so they got some mileage out of that one at least.
In mid-2003, Mark Lutz said he was in talks to appear in an "episode or two" as Groosalugg in late season four, but for publicly unknown reasons, the character did not return in the series. It was rumored that in season five, Harmony would have a "muscly hunks" calendar and Fred would recognize one of the models, as Groo.
Season Five
Harmony was brought back to fill the void left by Cordelia's absence. As such, it's possible that had Carpenter not left, Cordelia would have filled Harmony's role in season five.
After losing out on playing Jasmine, Morena Baccarin was later offered the role of Eve, but Fox wouldn't allow it due to her involvement in another television show at the time. This TV show never aired, and was cancelled after production on one episode.
When Buffy ended, Nicholas Brendon offered to move to Angel, but Whedon didn't feel that Xander would fit well into Angel's life and Spike was shunted over instead.
David Greenwalt, one of Angel's executive producers, wanted the main character of his own show Profit to reappear as a Wolfram and Hart employee. But due to rights issues and conflicts with Adrian Pasdar's schedule, the idea was scrapped.
Ben Edlund originally pitched Bad Horse of Dr. Horrible's Sing-Along Blog fame as an Angel villain. His reasoning was supposedly that; since horses on TV are usually nice, a bad horse would be really scary. Joss felt the idea was too silly to fit into Angel's universe. Then they did a puppet episode (which Edlund also wrote...).
Giles was going to have a guest spot in "A Hole in the World" but it would have been too expensive to get Anthony Stewart Head to fly from England - and so Drogyn was created to fill the role instead. Considering this, it's possible (but unconfirmed) that Giles was also originally supposed to be the one Angel killed as part of his initiation into the Circle Of Black Thorn in "Play Power Play", a role Drogyn ended up playing in that episode. This seems especially possible since Angel DOES end up killing Giles in the Buffy Season 8 comic, in the same manner as he killed Drogyn no less.
"You're Welcome" was supposed to feature her rather than Cordelia - and you can see the end of "Damage" foreshadowing a Buffy appearance. The plot would have revolved around Angel and Spike's rivalry over her. She had to cancel at the last minute, due to a death in her family.
She was asked to appear in the second-last episode "Power Play". However she was busy filming The Grudge at the time.
She offered to star in "Not Fade Away", but was turned down - due to producers not wanting Buffy to overshadow the rest of the cast.
Dawn was to star in "The Girl in Question" but Michelle Trachtenberg was busy filming Euro Trip, so the part was rewritten for Andrew Wells instead. Contrary to popular belief, Sarah Michelle Gellar was not meant to appear in the episode; the plan was always for Angel and Spike to only see her from far away. And the Season 8 comics revealed that it was an impostor dancing with the Immortal.
Season six and other scrapped sequels
Had the show got a sixth season, Illyria would have been split into Illyria and Fred, with Amy Acker playing both roles in tandem. This is the reason for the statement that Fred's soul was destroyed by Illyria's possession, which comes off as just being pointlessly cruel in the final version. The Fang Gang would have summoned Willow to perform the separation spell. Fred eventually did return in the post-finale comic series Angel and Faith, and she now shares a body with Illyria, as previously planned.
Oz would have returned, most likely to help Nina with her werewolfism. Seth Green has said he was never approached about that idea, so the story is up for debate.
According to Alexis Denisof, Wesley wasn't supposed to die. Had there been another season, he and Illyria would have featured in an arc in which the transformation of Illyria to Fred would have been extended over many episodes and taken to a "much deeper, darker place" than it briefly was in "A Hole in the World".
They would have progressed the relationship between Wesley and Illyria in such a way it would conflict with his own feelings for Fred, in a much more profound way. And then we would have gone into the switching of Fred and Illyria and having these two people that he was having these strong feelings about. That was going to be a fairly long journey in the following season, all of which got abbreviated tremendously when they decided to cancel the show.
After the series ended, there was a lot of talk about a series of made for TV movies with the characters, but no one wanted to fund them.
