Stainless steel requires less immediate cleanup, but can still rust if left wet. Carbon steels react to the foods being cut and turn all sorts of cool colors; blue, purple, golds, greys, etc. The steel will react until it settles in and forms a "patina", which helps reduce the reactivity of the steel. Carbon steels may discolor some foods, like onions, until the patina sets in fully. People often "force" a patina by acid etching the blade or covering it with mustard to make it react and settle down a bit before use. Both need to be dried fully by paper towel (no tiny water droplets left!!!!) when you are done using them. Carbon steel is a bit easier for a person to learn how to sharpen with, but some stainless steels like Ginsan/G3 and AEB-L are easy to sharpen. Same goes for the Fujiwara FKM stainless steel series; this steel is a little softer than many other Japanese blades, but it still sharpens easily and takes a very good edge.
Single edged knives are very task specific to traditional Japanese cuisine and are not the best for all around use in unskilled hands. Deba, Usuba, Yanagiba are the 2 popular single bevel knives. Stick to double bevels for now: gyuto, petty, sujihiki, nakiri, santoku! They are also not lefty friendly and often cost 30-40% more to make in a lefty version.
A honing rod for a European knife is not what you want to use on a Japanese knife. A typical Henckels/Wustoff type knife is much softer steel and the edge needs to be re aligned by the steel to keep it sharp. Japanese knives have much harder steel and the edge doesn't roll over and need to be aligned. A very fine ceramic rod, like an Idahone rod, or a leather strop, are all that's needed for touchups in between sharpenings. Some also strop on their finest stone as a touch up and by touching up the knife when it needs it, prevents the full sharpening for an extended period of time. I went almost a year on some of my knives at home between full sharpenings by touching up with stones.
A western handle is what you would typically see on a Henckels/Wustoff/Victorinox, etc; full metal tang and the little birds beak at the end, often with a metal bolster. A Wa handle is a stick like handle that can be Oval, Octagon or D shaped. The Wa is typically much lighter weight wise than a Western handle. As a lefty, look for a Western, Oval or Octagon Wa. Many lefties use a D shape handle and it doesn't bother them, some sand down the pointed D projection from the right side of the handle to make it more of an oval and others knock the handle off and flip it around so the D projection is on the right side. Myself, I prefer Wa handles, very few of my knives have western handles on them anymore!
For the Nakiri, I would look at a carbon one. Tanaka Kurouchi, Tojiro Shirogami, Murata, Zakuri, Yamashin are all very good Nakiri's for under $100. The more rustic looking knives may need the spine/choil rounded, but that's easy to go at home and takes a few minutes. I have the Tanaka KU at home, awesome blade! Very good performance, great edge holding, too. The Murata and Zakuri have oval or octagon handles, the Tanaka IIRC has a D, can't remember what the Tojiro and Yamashin had. I have a few Nakiri's at home and found that many of the lower cost Nakiri's perform almost as well as the much more expensive ones.
A santoku may be a bit redundant with a Nakiri. A Nakiri is made for veggie prep and push cutting veggies. It is not a bone cleaver, but a lightweight veggie knife that tends to slip thru veggies with ease. A santoku does well with veggie prep and you can rock cut with it more, but the tip is pretty blunt for fine work on many santoku's. I am going to suggest a Funayuki instead of a Santoku; they are generally pointier than a santoku and I like using them for a variety of tasks! Murata Buho or the Yamashin Funayuki are 2 great examples at a very reasonable cost! You could probably even skip the Nakiri and go with a Funayuki since they often have a good flat spot for veggie chopping and a pointier tip than the santoku. I often use my Yamashin in place of my Nakiri and petty for lesser food quantity prep, like if I need to cut up an onion, a couple of potatoes, and trim a steak or roast, I use the funayuki for everything instead of using 2 or 3 different knives. http://www.chefknivestogo.com/mufu16.htmlhttp://www.chefknivestogo.com/yawh1fu16.html
If you budget $100 per knife, the carbon nakiri/funayuki's will save some money, especially if you just go with the Funayuki instead of the nakiri and santoku. I would put more $$$ towards the gyuto since this is the knife people will generally use the most! The Yamashin Funayuki is $60 only, so I would open up the gyuto to the $150 range, maybe a bit more. Really opens up your possibilities!
Tojiro DP, Fujiwara FKM, Artifex, Kaneshige 240mm Stainless are the main choices for under $100 (Kaneshige is $110, close enough
). Going up a bit brings the Suisin Inox into play, the Goko Damascus (when they aren't on sale for $100) and a few more in the $150 range. Going up to $200 for the gyuto really opens the playing field!