Harissa and Ras El Hanout (North African staple spice blends)
Harissa - I have only ever bought/used harissa paste. I have a tube in the pantry (brand: Le Phare du Cap Bon) that I bought in a
Tunisian store and it can last on the shelf for years.

When I discussed the powder vs. paste matter with the guy in the
store, he said that they always use the paste at home, which I got
confirmed also from many other people. Anyway, I guess from the
amount you usually add to a dish, powder shouldn't make an enormous
difference as most ingredients in most harissas are dry (chilies,
cumin, coriander, salt, ...) and you can always reconstitute it into
harissa paste.

The paste I have is alright to add some heat, but it is not
particularly fancy ... there are definitely some more artisan
products available. However, for really tasty results I recommend
making your own at home - it will be so much tastier ... there are
tons of good recipes online (I personally like to add some more
cumin) - depending on the ingredients this might need to live in the
fridge, but in general harissa should be fine on the shelf.
Ras El Hanout mixes - they will have mostly the same ingredients (from the meaning "head of the shop" you can already guess that it
will include probably most of the spices from an arab spice shop ;-),
but there can be quite big variations in proportions of ingredients -
which might make them taste quite different. If you walk along a arab
market you find that Ras El Hanout varies quite a a bit from shop to
shop, and then between different towns, countries you get again
bigger regional variations ... and at the end it depends on your
taste buds which one you prefer.

But to start with - my guess would be that no matter which one you
get they will all add a similarly nice North African/Middle Eastern
touch to your dishes - if you feel adventurous enough you can get a
couple different ones for comparison (you can always give them away
as presents if you end up hating them ;-)
Saffron has a very specific flavor that you will very likely pick out, no matter how many other spices/flavors you add. But is it
really necessary to have it? - No, but it will certainly add to the
dish. And I guarantee that you will be able to find a ton of great
totally authentic North African recipes that have no saffron. And
about the expense - it really is not so expensive considering how
little is required for flavoring a dish and it will last for a long
time (stored dry in an airtight container).


Just an idea (in case you end up liking this cuisine) - make bigger batches of preserved lemons, so you won't need to wait for another batch to be ready. I make mine in a 5 liter spring top jar - so they last me for about a year (and a month or so before they run out I transfer them and start a new batch in the big jar).



Now the rest is just some hints - trying to answer your (broader) question before your edit:

Some spices that are quite traditional North African/Moroccan/East-Mediterranean (and are already often included in the available spice mixes) would be:


cumin
turmeric
paprika
chili
sumac
coriander
saffron
sesame seeds
cinnamon
cardamom


some spice mixes will also include:


cloves
caraway
fenugreek 


Some herbs that come to mind:


mint
cilantro
parsley


With this spices and herbs often some fruits and vegetables like lemons, olives, garlic, onion, fresh chilies and eggplants (often roasted or toasted to some extend) are the ones that add to the authentic flavors.

The savory dishes are often balanced out with some sweeter elements like raisins, dates and honey.

Some good condiments would be:


Dukkah ... it is super nice sprinkled on couscous.
Zahtar ... eaten with olive oil and bread.


Another nice ingredient is tahini  - sesame paste that is often used in arab countries (important ingredient in hummus and baba ghanoush).

There are some popular signature dishes that can be found in different subsets of the North African/East-Mediterranean countries: tajine, falafel, hummus, baba ganoush, ful, kibbe, shakshouka, kebab - meat skewers, tabouleh, mujadra and others.

Food is often eaten with different kinds of flat bread, couscous, sometimes bulgur or rice.

This is just some stuff that you can start with and slowly build on - and use in addition to your super exciting preserved lemons =D