I would say Khalid ibn Waleed but I confess that I don't know enough about history's generals to be totally unobjective. But the fact that the Prophet of Allah (saw) who does not speak but Revelation called him "Sword of Allah unleashed..." is a pretty unequivocal tribute to his legacy. Add to the fact that he was undefeated agains the Persians/Romans and it's as if when the Prophet (saw) uttered those statements Allah sealed the fate of Khalid ibn al WAleed.
Sir Lug,
That was actually Omar ibn al Khattab's remark about Khalid

the Shiekh was just using it.
Omar (ra) never used to allow people to weep openly in public about a casualty/death of the Muslims, but when Khalid died and the bani Makhzum woman started weeping and praising Khalid in public Omar was about to stop them and then he said (paraphrased): "Let them weep, for it is true whatever they say about him..."