Most complicated recipes call for a plethora of different spices, which can be very daunting especially when you've never used more than half of those listed before. It doesn't take more than a few hours of shopping to purchase all the spices you need though, and its all these spices that really define the taste of the dish. (e.g Satay?)
Fortunately for us, just about every spice that is commonly used in Chinese, Malay and Indian cooking is readily available all over the world. You can buy bottles of spices from any Giant Eagle? (e.g: McCormick?'s). There is also a speciality spice shop in the Strip, Penzey's Spices which has a large selection to choose from. See below for directions.
Some more obscure spices that you can't find in the above two locations can probably be bought at the ethnic grocery stores: Indian stuff from Kholil's? or Bombay Mart?, and Chinese stuff from Lotus Supermarket?. Kholil's has an impressive array of spieces of all kinds, but they come in pretty large quantities.
This is located a few shops up from Wholey's?, moving away from downtown. Apparently Google Maps tells me there's another one somewhere along Forbes, but I've never seen it before.