Regarding Vilnius as city overall it's very substantive thing - especially it depend to what are you comparing it to and what are your expectations, so best would be to plan some sort of visit and decide yourself how does it "feel" to you. Of course, it's not the most optimum option.
What can I tell you that having high education is quite common here and doesn't impress employers or get you the job. So what I would suggest is not to get into thinking that master degree will instantly get you the job. You will need work for it and try to stand out, since not days employers value mostly only work experience.