To be really specific, you do the betrayal quest and start through the Kelethin citizenship timeline. When you get to the faction building quests, pick "basic biodiversity" and you will get one of three or four random quests. If you don't get "kill orcs" then cancel the quest and take basic biodiversity again from the NPC until you get the orcs. The orcs are a 20 second run straight out the door, over the hill, down a tree and onto orc hill. Smite them, rinse and repeat. It might take three or four or even more tries to get the orc quest, but it is random. Just keep cancelling it and taking it. It's the easiest faction quest in any city.
Once you're a Kelethin citizen, go to queynos to the mage tower and take the citizenship quest, you pick up garbage, run around and speak to a few NPCs and you're done.