Leeds 03/04 wasn't that much of a surprise given how horrific the finances at the club were, & were selling everyone, the signings were based on revenue they'd get from being in the Champions League, failing to qualify for the second season in a row in 02/03 was catastrophic for Leeds.
Forest 92/93, they were still a good team, got to the FA Cup final in 91, many had them with a top 10 finish going into that season.
Crystal Palace 92/93, relegated in spite of finishing on 49 points, they were 5 points clear of the bottom 3 with 2 matches left, & ended up relegated, largely as Oldham won there last 3 matches to finish above Palace on GD
Sheffield Wednesday 99/00, were a decent team but shit manager, have not been back in the Premier League since, couple of playoff finals closest they've come
I wouldn't have Coventry as a surprise relegation, Coventry had been dodging relegation almost every season by winning there last match[es] of the season, that luck had to run out which did do in 00/01.