I was listening to Eliza's intro quotes and I noticed something, Eliza shit talks everybody.
Eliza objectifies Big Band, she threatens Cerebella, she claims Parasoul's kingdom, she doesn't acknowledge Filia and Squigly's existence, she calls Painwheel an abomination, she considers Ms. Fortune a pet, and more.
As expected she's condescending and dominating towards every member of the Skullgirls Cast.
However, despite all of this when Eliza speaks to Beowulf she says, show me your strength.
No insults, no witty jabs at his fashion sense, just a genuine interest in his capability. I might be plucking at straws, but maybe Eliza has a certain level of respect for great warriors. Maybe she respects the power of individual men and women who fight for the people, the paragons of the human race. As an immortal Eliza might have witnessed feats of ancient heroes first hand. Maybe she was impressed, and she hopes to be impressed again by this new warrior.