1) Get married
2) Send companions on RtR missions
3) Be part of a faction when peace is made
4) Smooth over relations between lords
5) Start your own faction and get truces
6) Be recognized as king by other faction leaders
I had decent RtR before I started my own kingdom. I actually chose to declare war against 2 other factions to retake Veluca and later try to retake Dhirim. I've been to war with everyone so constantly requesting Peace has gotten my RtR up very quickly.
Also, existing vassals prefer to receive a fief themselves. If you give a non-noble companion a fief, you'll insult some of your vassals. That said, I'd suggest you do it once and quickly. Setting up a group with Alayen, Baheshtur, Firentis, Borcha, Rolf, Lezalit, Matheld, and Artimenner leaves you with two non-noble companions; Borcha and Artimenner. I'd suggest setting one of them as your Minister and the other as your first vassal. Give them a castle and village and never give them anything ever again. After that, give fiefs to Rolf, Lezalit, and Matheld (and recruit Deshavi, Klethi, Jeremus, Ymira, and Bunduk) and later to Alayen, Baheshtur, and Firentis (and recruit Marnid, Katrin, and Nizar).
I'd also suggest you start the game by merchanting and building as many Dyeworks as possible for a reliable income. Join a few factions and change the balance of power. Getting high Honor means you have positive relations with most lords which may save you in a pinch, were you can beg not to fight another honorable lord and will be allowed to flee at the cost of a few relation points (those rejuvenate eventually)...
