I can't help with all of these but I know some of them!
1. Stoyan is the best (Science 75). Lorkas is also good (60). Chapadoc and Robe of Ice & Starlight Needle would theoretically be good (60 and 50 iirc) but I don't know if they can actually be persuaded to take cabinet positions. Both Lorkas and Stoyan automatically give you multi-node travel.
2. I think Mirelle on Myrkka II is the easiest first impression you can get to fast—she tends to like you even if you can't pass the etiquette test in her conversation. (Sometimes I go straight from there to Mau before going back to Myrkka I, but AFAIK that's only a good idea if you want to make Erilotti Chancellor—she's good enough to give the extra social action, but she's very hard to impress otherwise. And you need either a couple sessions of Spirituality or to have hired Mirelle as Logothete of Law to talk to Muistis at all, with that approach. But Myrkka II - Mau - (Myrkka II again) - Myrkka I does give you a few more turns to build up skills to impress the Myrkka I characters.)
4. I think yes, Lukomir always announces on the same turn. (... Someone else please remember what turn it is, I'm only half sure I have the right number in mind.)