I think King Hereafter, prose-wise, is by far Dunnett's most difficult. I also found it less, well, romantic, in nearly every meaning of the word. Brilliant, yes. Accessible? By no means.
Susan, I would suggest giving Game of Kings one more try; if that doesn't work, skip forward to Disorderly Knights, which moves faster and gets into the uber-plot more quickly as well. Also, the first section of that novel has one of my all-time favorite set-pieces. Heh.
Once you've settled into the universe, it's not as hard to go backwards and see what Lymond was up to beforehand. I wouldn't recommend starting with any of the others, though: the later books are too arc-dependent, and Queen's Play is kind of problematic (I find).
Nutty, I read Ivanhoe as a kid, and the Three Musketeers, and yeah, found them romantic only in the swashbuckling sense, not in the the, um, investing-in-the-relationship sense. Dunnett does both of those for me; not a lot of other novels do.
Betsy, when does Captain Alatriste get released in the US? And did you see the link to the promo shot on LJ?