Having though about this some more, I'm not sure a lack of history between the characters is the problem, really. From the minute we see Vader in ANH, he has presence as a villain. Maul is just a flashy martial artist with a stock movie villain voice, a painted face and a double-bladed sabre. He (IMO) has no villainous presence whatsoever (and I'm not sure why Vader works, but he does).

I suspect that if Vader and Obi Wan didn't know each other in ANH, and just had their slow sabre battle in silence, it would still have been more engaging than the Maul fight - but I'm not sure why. Perhaps it's as simple as Obi Wan giving the others a chance to escape - whereas in Menace, it's just a fight for the sake of it. Or perhaps it's just Alec Guinness's screen presence (and Vader's screen presence; as I said, IMO Maul's got nothing)?

I'd be very interesting to hear what everyone else thinks about this.