My opinions, tendered on the understanding that no solution will be truly adequate:
Brus, Stewart, FitzAlan, FitzStewart, FitzWalter.
"Fitz" seems to me (like "mac," perhaps) to be of a different order than "de" and "of." As far as I can tell, the FitzAlans at least are using "FitzAlan" consistently almost as a surname from an early date. (I don't have the same knowledge of FitzStewart and FitzWalter as I do of FitzAlan.)