I'm not sure there would have been much of an ideological gap between these two. But Clinton would've won easily. Powell wouldn't get as many states as Dole, as places like Mississippi, South Carolina, etc, would've gone to Clinton.
What makes you think that the south wouldn't have been ready to vote for a black Republican in 1996? A black Democrat would have had zero chance to win the south and a black Republican would not have done well in the primaries, but I can't see any large scale white flight to Clinton. At worst, those voters would have gone to Perot, and Powell would have easily been able to attract enough moderates from Clinton to make up the difference. Powell would have done better than Dole, but not enough to win the election.
States in green are Powell's pickups over Dole.