Not sure about the neutral stuff, but I can tell you that if a Computer Player (CP) is neutral to you they will not attack your villagers but they will attack any military units i.e. everything else.
I can't remember exactly how the allied victory works, but if you select it I think it means you lose if your allies get killed or something. If it's just you against another CP then allied victory is pointless unless you plan to win by capturing artifacts (or ruins) or by building a wonder, but if there is more than one CP I think they can win for you on allied victory if they destroy the enemy. I'll have to check that though, I could be wrong, the only time I really play with that is in a scenario I design myself, where the Victory Conditions are normally specialised anyway.
Tribute is easy enough. You cannot tribute without a market, then you go to the diplomacy screen and offer food or gold or whatever to the CP you want to ally with. Unless you are Palmyran though, it will cost you a bit on top, like a fee, to tribute another player.
However, the CP may not always ally with you, in which case you get a message saying something like "Your puny attempts at bribery will not stop me from crushing your empire", in which case you are resigned to enemy status. Either way you will get a message saying how the CP feels about your offer. My favourite is when a CP asks you for tribute and then, when you pay, says "You have made a wise decision. Together we will rule the world." That won't happen in a RM game though, because the files used to decide the CP's behaviour are not set to ask for it, but you may find it happening if you download and play anything from the Granary.
One thing - just because you select neutral or ally in the diplomacy screen, that doesn't necessarily change the CP, that's just really telling the CP how you feel about them.
If I remember anything else I'll post it to this thread, but I'm sure all the nice people here can add to it.