hard to tell with all the different eras in starcraft history. and that's just by looking at best in brood war, WoL, hots or lotv. to name a best guy overall is next to impossible imo.
flash would be the most common answer for brood war and he's certainly among one of best picks for that position. players that can match his achievements/titles are few: nada tied in titles, jaedong with 5 & savior with 4. sorry, no protosses.
as far as who changed the game the most, i'd say it's uncontested with savior taking it. against hardest competition, against most unfavorable map pools for zergs, he'd find ways to win and keep on changing his builds & meta.
other legendary names that ring the most bells and are credited for what brood war is/was are Reach, nal_ra, iloveoov, boxer, yellow and bisu.
as far as sc2 goes, i've no idea. each exp has so much balance patches that shift the meta + each exp is a completely unique meta and it's quite hard to tell. if i'd have to pick a name it'd be the king of wings, IM MVP. i've no real reason why, back when he won his 4 gsl's the competition wasn't all that much and the game was still evolving rapidly, but for me he was THE reason to watch sc2 along with brood war (instead of just watching brood war).