One of the biggest misconceptions among the Fullmetal Alchemist fandom is that Roy and Edward's relationship is mostly based on rivalry and/or animosity. I couldn't disagree more with that interpretation. What you first need to understand, in order to begin analyzing it, is that Edward holds a deep grudge against his father.

Hohenheim left his home when Edward was barely 5 years old. That same year, his mother died, leaving the two brothers alone (under the care of their neighbours, the Rockbells), with no clue as to where his father had gone, nor if he would ever return. It was at that time of desperation, when Ed and Al decided they would try to bring their mother back through alchemy -- which they started learning with the help of their father's books. Edward never tried to find his father's wherabouts, after all it was him who ran away, left his wife and wasn't even present at her funeral.

Edward thought he could take care of himself and his brother while at the same time bring their mother back, he didn't need his neglecting father for anything. He also thought that human transmutation was forbidden, not because it was something dangerous, but because no adult had been able to succeed at it. Oh, how wrong he was.

Not much time after Ed and Al's attemp to revive Trisha, Roy and Hawkeye arrived to Resembool in search for two potential national alchemists. What they found there, though, were two broken children with no hope for their future. Roy then offered them a way out, a possibility (even if small) to recover their original bodies, or at least the means to try to do it. Roy, as always, wanted to make sure no one was doing anything against their will:

Roy: Mrs. Rockbell, I'm not trying to force them to do anything. But I'm only stating the possibility! To live your life with hopelessness and a piece of armor for a brother, or to sell yourself to the military for the possibility that you can recover! It is your choice.

Edward's wound was still fresh (in both his body and his mind) and so he didn't say anything at the time. However, Roy could see determination in his eyes and was sure the boy would accept his proposition. And he did. Right after he recovered, he went to Central City and became a National Alchemist. From that time on, he would be under Roy's command.

Considering all this, it's obvious where Edward's problems with Roy would have started from. The colonel is an adult, an authority figure and a talented alchemist, all at once -- all things Ed identifies his father with. Not only that, Roy's behaviour towards Edward is very much parental, at least in the way the military allows him to be. Roy not only protects Ed's secret about his attempted human transmutation, he also protects him from the rest of the military, allowing him much more freedom than any soldier can have.

This interaction is not easy for any of them. Roy is torn between his desire to protect an orphan kid, and his duty to treat him like an adult, like a soldier. This is also a consecuence of Edward's own mixed personality. He'd like to be treated like an adult, but has to deal with the fact that he's not one yet, and that he must accept help from people who're willing to give it.

Edward's child self is more evident when we observe just how much trouble he has accepting parental figures. Hughes was not attempting to be one, he just supported them and acted like a friend, kindly and trying to ease the brother's problems. Roy, however, is the most resembling thing to a father in Edward's head. Despite his willingness to protect and help them, he's also strict and trying to make them learn things, even if through the hard way. The problem is that Roy didn't know where to draw the line between being totally honest with Ed and protecting him.

Hawkeye: Seems like you only treat them as children at this time?
Roy: They don't need to know about it today. It will be best if, as much as possible, the brothers have few hindrances to their progress. It seems... I am not able to call Major Armstrong a good person anymore.

This ended up hurting the already damaged trust between the two, more than anything. Because, if there's something hurting to their relationship, is the fact that Edward's automatic distrust for authority/parental figures makes him blind to realize just what an incredible ally Roy represents to his brother and himself. This situation did not benefit any of them, and so Roy realized that in order to help the brothers and be helped by them he had to make clear they could trust him. Soon after the Maria Ross set up, which became the biggest confrontation between Ed and Roy, the colonel decided to end this path of distrust, once and for all.

When Ed was led to Ross' current whereabouts, we learnt something quite interesting from him. He had ended up believing that Ross could in fact had been Hughes' murder. If you think about it, it's only logical Edward would trust Roy more (someone he's known for four years approximately) than Ross, with whom he had very short interaction, however nice and trusting she seemed. He disapproved of Roy's methods in avenging his friend and was angry at his attempts to hide Hughes' death from him, but chose to trust Roy's judgement either way.

After having been trusted with all of Roy's discoveries and investigations, Edward is finally able to openly admit that Roy is someone he and his brother can rely on, and work with him to achieve their goals. Of course, Ed's behaviour towards Roy is not gonna change anytime soon and the fact that he represents the closest thing to a parental figure in his life, still annoys him.

Something that probably also annoys Ed very much is the fact that in certain aspects, Roy and him are quite alike (as Alphonse already pointed out). The moment someone they love is in danger, they forget about themselves and do whatever it is they need to protect them. Anyway, Edward's new-found trust in the Colonel and Roy's final decision to try to treat the brothers like adults only from now on (while protecting them at the same time), have helped improving their relationship a whole lot:

Edward: You do your work. The top of the military being a homunculus isn't a problem you can just leave alone, right? [...] We are the ones who came up with the plan this time. We have to clean up after our own mess. Thanks for lending a hand up to here.

Also Edward's latest burst of maturity is something refreshing which has helped quite a bit. His understanding of Roy seems to be increasing, as he proved when commenting about Havoc's current situation and not pushing the subject of Ishval when Roy didn't look like willing to talk. Took the boy long enough, though.

As for their supposed rivalry, it's something which comes from Edward's side only and it's not even that strong anyway. It's probably due to the fact that Roy, in addition to being that fatherly figure Ed seems so unwilling to accept, is also one of the strongest alchemists he knows. His wish to prove that he doesn't need anyone to look after him and to prove he's strong, is what makes him challenge Roy in the "Flame VS. Hagane" gaiden.

Of course, Roy is a more qualified alchemist and calmly shows it to Edward. The man has a 14 years advantage to begin with and quite the confidence in his ablities, something which doesn't prevent him from acknowledging that Edward is in fact a boy genius.