Strange Titles and Alternate Names
I try to do this in my Wessex reports. Òengus isn't just some magic-user, now he's Òengus the Somnomancer. Philip of Luxembourg is also Philip the Black also Philip the Bloody. Father Jack is The Drunkest Priest in Cornwall (no mean feat). But it also can occur naturally, such as when Redwall the Thief became Boner the Pig.
"You used to adventure with a psycho clown who played an accordian? Me, too! We looted a mummy's tomb together in the next universe over." [proceed to get stinking drunk together]
Knickknacks from Other Dimensions
Even something as prosaic as a bucket of lard can be special when it comes when a distant world.
Something to Swear By
More players should pepper their in-character speech with their own custom battle-cries or bloody oaths. "By Crom!" "Demon dogs!" etc, etc.