Depends on what you're looking for. I haven't handled any of these knives, but have read a lot of opinions and impressions on the Police and the Military.
The Police is one of Spyderco's first models, and has improved a lot over the years. It is slightly longer than the Military, yet it's intended for many applications, including "general Police work", whatever that means. The Military, however, is a workhorse of a knife...it will keep cutting and cutting and won't give up when you expect it to. Also, it looks much bigger than its weight...people say it is an extremely comfortable carry. No wonder it's considered a flagship Spyderco model by most people. It's a tough choice, but I would go for the Military. I wouldn't even consider the Viele, since it's just not my taste.
As for handles, go for G-10. Steel handles certainly look nice, yet they scratch easily and are very uncomfortable. Plus, G-10 is designed to handle any tough situation, and is not affected by heat or cold, whereas steel handles certainly are affected. Also, G-10 handles provide great traction for the hand while doing heavy cutting chores, with a great "grippy" feeling, whereas the steel handles get slippery with sweat or any other liquid.
As for me, I had to decide once between the Military or Starmate. I chose the Starmate, since I liked its aesthetics, and really think that it possesses a great balance between tactical and utility use. Handle is also shorter...I really dislike handles which I consider too long, since my hands are not too big. That's one of the reasons I have yet to get a Military.
In conclusion, I consider the Military and Starmate to be Spyderco's best offerings in the "almost 4-inch blade" category. If I eventually consider getting the Police, I would probably do it after getting the G-10 Military, and I would choose a stainless steel model just for aesthetic purposes. Also, I really like the looks of its hollow ground blade (only offered in steel handle models...G-10 models feature a flat-ground blade).
Hope this helps!
-Flood
------------------
HERMES: "The Applegate Fairbarn is not bad...but for both offense and defense, the Randall 14 is good."
HERMES: (Admiring the Joe Kious Sub-hilt dagger) "I'll take the Joe Kious for a friend."
KNIFE-SELLER: "Excellent choice."