"Is there a clear distinction at all, or is the border between the two groups somewhat fuzzy? Or are omnivores merely herbivores who are less picky?"
On second thought, I'll tackle those questions.
The "border" between herbivores and omnivores is very fuzzy among mammals, birds and at least some reptiles. Amphibians are a treat - they're all carnivores. Among reptiles, snakes are exclusively carnivorous.
Most lizards are also carnivores, though there are some herbivores. I'm not even sure about omnivorous lizards, though.
Omnivores are all over the map. If some are described as herbivores that are less picky, others could be described as carnivores that are less picky.
Note that certain species can be herbivores, carnivores or omnivores in certain parts of their range or during certain seasons. For example, bears may feast on salmon or ungulate calves when they're available but spend most of their time foraging for plants and small animals.
The most familiar omnivores include humans, pigs, raccoons and (some) rats, so you might look for some similarities between these species. Humans and raccoons are plantigrade, for example (as are bears - and rats, too, I believe). Humans, pigs and rats are known for their intelligence. Pigs and rats are very popular in medical research, for some interesting reasons.
Another thing to note is species that defy their group's general dietary tendencies. For example, the giant panda and palm nut vulture are herbivores, whereas other vultures are carnivores and most bears are omnivores - except for the polar bear.
There's another general rule; omnivores may be more rare in habitats that are lacking in plants. I don't think any marine mammals are considered omnivores, for example. All cetaceans (whales and dolphins) are carnivores, as is the sea otter. However, sirenians (manatees, dugong, etc.) are all herbivores.
That might give you something to work with.
EDIT: To my surprise, there are some good resources comparing omnivores and carnivores. Check out The Comparative Anatomy of Eating. The source might look a little flaky, but it looks very accurate to me. (It uses some of the same examples I did. ;))
To my surprise, there is apparently a closer correlation between carnivores-omnivores than herbivores-omnivores. But bear in mind that this article apparently focuses on mammals. Thus, differences in jaws and teeth can hardly be applied to birds.
Regarding my comment on omnivore intelligence, see Intelligence, Evolution of the Human Brain and Diet, though I can't vouch for its accuracy. Intelligence can be related to diet; it takes more brainpower to capture active prey than sneak up on a clump of grass, for example. This would suggest a preponderance of "intelligent" organisms among carnivores.
Intelligence can also be related to anatomical differences, like bipedalism, opposable thumbs and binocular vision.
In fact, most of the animals that are renowned for their intelligence appear to be carnivores or omnivores. Exceptions include gorillas, orangs, gibbons and the giant panda.
While whales, wolves/dogs, squids and octopuses are carnivores. Crows and ravens - regarded as among the most intelligent birds - are omnivores, as are humans, chimpanzees, pigs and at least some rats. As far as I know, pigs are generally regarded as the most intelligent ungulates (hoofed mammals); they're also among the few that are omnivores. (I can't think of any other omnivorous ungulates offhand.)
Pigs are also more compact than other ungulates, with stocky bodies and short legs. In fact, there don't appear to be many long-legged omnivores (among mammals, at least). Similarly, most (if not all) long-legged birds are carnivores (or insectivores, vermivores, etc.).