My main goals are to build more muscle around my abs, arms, back, shoulders, bum, and inner thigh area to look slender and good. Although I don't want to get bulky and get massive legs.
First things first: it is hard to get bulky. It is hard to get massive legs. It is hard to achieve a bodybuilder physique. I hear this woe a lot, disproportionately from women, that achieving massive muscly legs is something that might happen accidentally. World-class bodybuilders, men and women, train and eat consistently for years to achieve their physiques.
I say this because this fear of being "bulky" causes many women to fear lifting heavy. However, lifting heavy is exactly what you should be doing to achieve your toned physique. I think you should take some time to read through these questions and answers: How can I get more "toned"?
Quoting this answer:
You need to lift weights like you're trying to get big - just don't eat like you're trying to get big.
On the topic of food: yes, you should be eating protein. How much depends on your goal and I will direct you to this great answer: Protein: How much is too much?
You've stated that your goal is to build muscle. If that's the case, your body needs protein and calories to work with. You should definitely be eating more protein than "sedentary" but while you're working on building up that muscle I think you should aim for somewhere between "active" and "bodybuilding".
In terms of calories, you should track your food and aim to eat about 200 calories more than your total daily energy expenditure (TDEE); this is just the amount of calories you burn in a day + activity. Eating slightly more calories than your TDEE will help encourage your body to build muscle while keeping the excess fat away.
I definitely suggest weight training first and then doing cardio afterwards.