Animals are often about smells and scents. Cats rub their head against your leg because they are smearing their Body Odor (so to speak) on you to claim you as territory. You'll see them rubbing their heads on walls, sofas, trees, doors, etc. When I had three cats, it was the Alpha cat (the one who didn't cover her litter in the litter box) who seemed the most territorial.
Dogs are very social creatures, like humans, and they sniff each other to get a sense of the scent. It really is like saying "Hi, how are you." It's there way to get a feel for the creature (they even sniff human behinds too) to decide if this thing is a threat or friendly. It's also their way of bonding with something. I think they start to sniff you out before you even recognize them sniffing. They have two sniffs. Ground sniffs (which they can smell for a long time after you walked there) and air sniffs. So they smell you coming long before you see them, and they are getting a feel for you there too. Then, when they decide they like you that far and are still curious, then they sniff your butt to really get a feel for who you are. I'm sure territory plays a role in there somewhere, as they are more apt to sniff out stranger butts in their house to distinguish what items in the house smells like a stranger and what items smell like their master to get a feel for what is shared territory. Have you ever went to someone else's house, and the dog is friendly with you until the person takes you to their bedroom or a room that is uncommon for a stranger/visitor/guest to enter? They do that with other animals as well. They want to get to know an animal's scent to figure that animal's territory. But also, especially for mating between the species, it's a way to get to know somedog.
People kinda do it too I guess, like most wives know their husband's body odor smell, and many kinda like it. Even if it's not the BO, many women find comfort in smelling the cologne their father wore after their father dies, or same for an exboyfriend they loved after the break up. That's why we like to wear their old clothes, especially if they hadn't been laundered since he wore it. It's like an instinct we never really think about.
But, I will say, there are rules in the animal kingdom, or a social etiquette. Every species seem to have their own set of rules, and the more you know about them, the easier it is to get a long with an animal stranger. Like if you know a lot about dog behavior, when you go to rob someone's house (not saying you would, but hypothetically) who has a Rott, then you know in order to work around the Rott, it would be best to visit before hand pretending to be a Jehova Witness or something in order to get that Rott to know your scent and make sure you mark your territory while visiting Seriously, there are real benefits to knowing certain behaviors and rules. Cat haters would benefit knowing things like constant attention from strangers to a cat is intimidating, and that's why they always seem to rub all over and hang around the guy giving them the least amount of attention (usually the cat hater) because they seem less intimidating. Dogs I think are intimidated when you look them in the eye, so if you are trying to show your dog whose boss, sticking your face in his without fear would do better than yanking on his chain while someone who fears dogs would be best to not make any eye contact at all.
What I also think is interesting is that a veterinarian once told me she preferred male cats to females because females were more temperamental. You can see that with humans so well too. She was purrfect proof of that as she was one of the most temperamental veterinarians I ever had the pleasure of knowing.
I used to have 3 cats. I ended up giving them to the humane society (in tears) when I moved across country back home because it seemed impossible at the time (long story) to take them with me, but I was going to give them to friends when I moved home anyway because they were getting territorial over the babies, and I couldn't have that, especially when urine plays a role in territory. If they could have left it with wiping their spit everywhere, I would have lived with that. I used to feel guilty about it, but now I realize if it were sheer animal kingdom rules, we would have fought to the death over that territory and being at the top of the food chain, I would have won. So, giving them away was more humane. I still wish I could afford a place big enough where territory could have been easier shared.