I'm in the same boat as you Maya, except I never wore make up much before and therefore have zero skills to start from I just started dabbling in this myself this past month or so, but I'm not approaching it from a full face standpoint; my skin is fairly clear, and my lips (and cheeks to a lesser extent) have a lot of natural color. I too have large features (mainly nose and lips), though my skin is lighter and I think my hair is much thinner (whole different topic). Having built in contrast and large features does, as others have mentioned, seem to minimize the impact that make up has. I decided that I could get the most drama if I played up my eyes, so I'm working from there out.
Right now, I am able to competently apply mascara (I have thick dark lashes, but LOVE how mascara highlights them further); in the last 2 weeks I've been able to semi-competently apply liner and am experimenting with color/texture, thickness, and how far along my eyes to go. It's been interesting and I like the results so far; it's enough of a change, and enough additional polish, to keep me happy and therefore I'll be likely to continue with it. I'm not sure if I'll expand from here, I'm still pretty slow at just these 2 things.
I hope your Aveda order is grand, I think that blue liner will be fun and look great on you! Wish you luck in this endeavor, and I'll be tuning in to hear your review and how your new regiment goes