When people refer to Belichick as a genius, I take it to mean he is a genius of a football coach, and not a genius in general. That is pretty hard to argue against, since he has been a major part of five Super Bowl champions (3 as head coach, 2 as defensive coordinator) and an AFC champion (1996 Patriots).
Was his Cleveland tenure rocky? Yes. At the time, I believe he was the youngest head coach in the league and he was taking over one of the worst, if not the worst, Browns' team in franchise history. Kosar had huge status in Cleveland at the time, but the change did benefit the team, regardless of whether Cleveland fans liked it. When a major, wildly unpopular change like that is made by a person with the personality of messy underwear, it's not going to be received well.
Still, the Browns went from 3-13 to 11-5 within 4 seasons. Only Pittsburgh, the team that knocked the Browns from the playoffs in 1994, had a better record among AFC teams that year.
The fallout from the 1995 season is pretty hard to pin on Belichick. The franchise move undermined anything done on the field that year.
By no means did Belichick run Bledsoe out of town. Bledsoe suffered a major injury, and Tom Brady stepped in and led the team to a Super Bowl. At the time, Bledsoe was too good a player to stay as a backup, but there is no way any coach could have logically decided to go back to him over Brady.
As was the case in Cleveland, time has shown that Belichick made the correct decision for his team.