Time loops are always tricky.
We have a couple of possibilities here:
1) The Future Bill & Ted we see never met their future selves (this theorizes that the Future Bill & Ted we see is the first copy who initially enter the loop). In this scenario, Rufus had to have introduced himself to them. Or did he?
2) The Future Bill & Ted we see met their future selves and are told Rufus' name. But this assumes that someone, at some point is introduced to Rufus - and NOT by any version of Bill & Ted.
Two people meet him - and refer to him by name - and are NOT introduced to Rufus by any version of Bill & Ted: the princesses.
Ted: We looked all over England for you.
Bill: Where'd you get those savory clothes?
Elisabeth: Rufus introduced us to a place called the mall.
Flora: And something called credit cards.
Rufus: I got them out of England just before they had to marry those royal ugly dudes.
Rufus was not in England with Bill & Ted. He went there separately to rescue them and by this point has clearly introduced himself by name to them.
So even if Rufus never introduced himself to the original Bill & Ted, they still learn his name from the princesses.