Grue said:
Enter the Fremen. Paul beats one in personal combat (Jamis in a knife fight) fairly early in the novel. Paul was trained by his House's Swordmaster (Duncan Idaho is regarded highly by the Sarduakar in the novel I believe... equal or slightly better than the best Sarduakar).
By the time he fights Jamis, Paul has also trained in thw wierding way of battle - a special combination of Bene Gesserit training and highly advanced swordfighting techniques. He is far
far superior to a Sardaukar by that point. (So is Idaho, actually. In later books, you find out that when Idaho died fighting to buy Paul and Jessica time to get away in
Dune, he killed something like 17 Sardaukar before being killed).
The Fremen are described as people raised in a harsh unforgiving enviroment, with significant times of shortages and deprivation. At that point I gotta put on the blinders (and why I prefer wierding modules better than Xena warrior fremen for a scifi movie). Harsh low caloric conditions don't produce humans that are better warriors. They produce smaller, leaner, and presumably physically weaker people able to survive on less calories (and less water... smaller people also can handle heat better... considering the ecology research FH put into the novel... heh).
The theme of the book is that harsh conditions produce tougher people. Training alone cannot make a person a superior warrior in the
Dune universe, people have to spend their entire lives being tempered for the job. (A theme that runs through a lot of
Dune = human perfection has reached such a level that most people must spend their entire lives, or even mutiple generations, to excel at their chosen work). The concept of "Amtal" or testing something to its breaking point, is talked about a fair amount in the book.
(One way that Paul is exceptional is that he is good enough to be good at several things, something that almost no one else in the book can accomplish).
Also, remember that the Sardaukar are supposed to be trained in similar conditions to the Fremen on Salusa Secendus - which is described as a hell world. So any "low calorie harsh conditions" are likely to be shared by them.
Fighting skill.... lets say the Fremen have slightly superior skill (remember the novel places them roughly equal).
Until, of course, Paul shows up and shows them better ways to fight.
On its own terms, the book makes sense. Of course, the book assumes that humans can be trained to work as fast as (or better than) computers, people can see the future, and navigating the stars requires the use of a spice found only on one world. Saying "people raised in the desert doesn't make people tougher" is simply not taking the book's premises as presented. In the book, it does.