I'm making some pasta at home with a pesto sauce. The recipe I'm referring to asks for some basil leaves to go along with the pine nuts in the food processor. Unfortunately, I can't find basil where I live, and I'm looking for a something else to put instead. What's a good substitute? For that matter, what does basil taste like -- is it like spinach?
The good news is, you can make pesto almost out of any green using the same process and proportions as with basil -- it just changes the flavor profile. I make pesto-style sauces out of chives, cilantro, kale, arugula... I would not be surprised to find you could make a spinach pesto. Basil tastes very different from spinach, though.
If we're talking about the big classic pesto alla genovese, then unfortunately...
There is no substitute.
Basil is the majority ingredient in pesto. None of the other suggestions here will taste even remotely similar. You'll be making a completely different dish entirely. It will be some type of vegetable/oil paste, but it will not taste anything at all like pesto.
It would be like trying to make baked beans without beans, or french onion soup without onions. These ingredients are so dominant and so essential to the flavour of the dish that there's literally nothing left without them. Just forget about it and make something else. It won't be pesto without basil - not even close.
Critically, if you're using this pesto as a component in a larger dish then it definitely will not come out correctly with any of these substitutions. Pesto is used in a lot of ways and every recipe that asks for it is expecting the flavour profile of a basil pesto. No substitution will be effective in this case, and each recipe that calls for pesto will have its own unique flavour profiles that will clash in various different ways with each of these substitutions.
If you're desperate, whatever substitutions you do end up making will depend heavily on what you're ultimately doing with the pesto - what you're pairing it with. We don't know what that is, so it makes it that much harder again to make a reasonable suggestion.
There are a lot of varieties of basil, that have some subtle differences in taste, but there's usually a mild background of licorice. (And honestly, basil was ruined for me for many years after my mom mentioned it, because I hate licorice.)
oregano OR thyme OR tarragon OR summer savory OR equal parts parsley and celery leaves OR cilantro (This works well in pesto.) OR mint (especially in Thai cuisine)
Personally, I'd just go with flat leaf parsley or some other tender, mild green leaf, and a bit of oregano and/or tarragon. (but only if you can get them fresh, do not use dried herbs for pesto).
You could also consider making some of the other varieties of pesto, as not all use basil.
Good news for you: you can make pesto out of just about anything. The word "pesto" actually refers to the manner it is traditionally made (with a mortar and pestle) and shares etymology with both "pestle" and "paste". And that's basically what a pesto is: a paste. In English-speaking countries, "pesto" is typically used to refer to pesto alla genovese these days - the one you're probably thinking of, with basil and pine nuts and olive oil and cheese. And if you're looking for something as close to that as possible, there's lots of great advice in the other answers about herbs you can substitute for basil. But feel free to be inventive! Pick your favorite herb, whichever nuts you like the taste of (or none at all), add garlic oil instead of olive oil... whatever suits your fancy. Rest assured that your own recipe is just as authentically a "pesto" as anything you can buy in a jar.
A personal favorite of mine is to use sage and ricotta. I've even seen pesto made with cilantro (and for those of you who have cilantro soap mouth, note that pulverizing the cilantro denatures the chemical that causes this unpleasant taste for you).
And while we're on the subject, if you want to learn a ton about pesto the first episode of the four-part Salt, Fat, Acid, Heat miniseries (the "Fat" episode) covers pesto. It's a good watch if you love Italian cuisine.
I'd look at making Chermoula, which is based on cilantro, and cumin. It's also a paste, useful as a sauce or on its own. It's delicious!
Here is my go-to recipe: Chermoula
1 teaspoon cumin seeds, toasted 1 teaspoon coriander seeds, toasted 1 cup cilantro (small stems ok)
1 teaspoon fresh ginger (a thin slice about the size of a quarter)
3 garlic cloves 1/3 scant cup olive oil Zest from 1/2 lemon (about 1-2 tsp) 2 tablespoons lemon juice, preserved lemon optional 1/4 teaspoon cayenne 3/4 teaspoon salt, more to taste 1-2 fronds saffron 1 red arbol/cayenne chili, deseeded, chopped.
Toast seeds in a dry skillet over medium heat, stirring until fragrant and golden.
Coarsely chop the cilantro and parsley. A scissors is a good tool for this; point it tip down in the measuring cup and cut the leaves. Then place them in a food processor and chop very fine, or chop on a cutting board. You should have 1 cup finely chopped herbs.
Place the garlic and salt in a mortar and puree. Add a small handful of the chopped herbs, and gently but firmly grind until the herbs begin to dissolve. Add another handful. When all of the herbs have been mashed, work in the spices, 1/3 cup olive oil and lemon juice. Taste and adjust seasoning. Add more olive oil or salt if desired. Serve with grilled fish and/or vegetables, or with chicken.
I have used garlic mustard in a pesto recipe. It was OK but it was not pesto. I don't plan a repeat.
We have too much of it; it's invasive.