Arena:Random Quests

All of the quests in Arena outside of the main quest are completely randomized. The names, places, and times are changed, and the quest task can be one of several types. Each task is added to your quest log and in versions prior to 1.07 the storage space is limited. When the file is 2,000 bytes or larger, the oldest message is removed before adding a new one, so it is a good idea to print it out from time to time to help keep track of things you are supposed to do.

Artifact Quests
This type of quest is fairly rare. But sometimes, when asking about general rumors, you may be directed to a person who knows the location of an arcane artifact. The chance to receive an artifact quest increases by 2% for each character level up to the maximum 20%, and there is just a 50% chance an NPC will talk about the rumors at all. These quests start the same way as delivery and escort quests. Travel to the pub, talk to the bartender, and be approached by the person. You will have to pay a small amount of gold for the information.  The person will direct you to a dungeon somewhere outside of the city walls. Travel through the dungeon and find the artifact. You may now use it until its charge runs out.
You may not have more than one artifact at a time (although there is an exploit that allows you to do so). Therefore, if you have an artifact in your inventory, you will not get another artifact quest until the one you have disappears.
The artifact is randomly chosen from the pool of sixteen, minus the ones you have using the exploit. The chances of one particular artifact being chosen is 6.25%.
If you choose not to pursue a particular artifact, you will not be offered it again for a long time.
The artifact and its map are always located in a chest in the bottom floor of the dungeon.
If an NPC says that they've heard nothing interesting going on lately, or something similar to that, they probably will not give you an artifact quest, no matter how many times you ask them for rumors. 
Once you've located an NPC willing to talk about rumors, asking them for rumors repeatedly (usually within twenty tries) will yield an artifact quest.
When searching for artifacts, it is usually best to ask around in the Imperial City. This is because all NPCs can only give you quests for artifacts not within their own province. Since no artifacts are located in the Imperial Province, an NPC in the Imperial City can give you a quest for an artifact from any province.
If searching for a particular artifact, it is usually best to find out which provinces that particular artifact (and any of its map dungeons) can appear in. Then simply go and ask for the artifact in a province that will never contain it.

For more information on artifacts, see the Artifacts page.

Capture a Criminal
This type of quest involves capturing an outlaw. The king or queen of a city will ask you to retrieve a criminal from a certain dungeon (the dungeon should have the same name as the criminal). When you find the criminal, attack him and he will fall. The criminal won't actually die, and you now have to escort him back to the person who gave you the quest. You will then receive your reward (30-50 gold per level, depending on the city size).
This quest can be dangerous, as the criminal shares his dungeon with a random monster (ranging from a Minotaur to a Lich, regardless of your level).
The chance to receive this quest improves with your level.

Retrieve or Deliver an Item
This type of quest requires you to travel to a foreign town and retrieve or deliver an item. These quests are offered by a king or queen found in the palace, and, like the above capture quests, require a high reputation. You will be attacked by an outlaw faction (Thieves Guild, Dark Brotherhood, possibly others) if you try to rest in a tavern during one of these quests.  If you are level 10 or more, you'll be able to do most of these quests. There is a 5% chance per level for kings and queens to have quests available for you. If not, try another town, another province, or try later.

Delivery/Retrieve or Escort Quests
These are generally the easiest and fastest quests. You can start by asking about Rumors and then choosing the Work subtopic. The person will either say they haven't heard anything, in which case just move to a different corner of the city and ask there, or tell you about someone who currently resides in a pub and wants someone to work for them. When you reach the pub, talk to the bartender. You will get a message that an individual has pulled you over and given you the task.

Generally, these quests require you to take an item or a person to a landmark in the city before a certain date (which is two days from the time you receive the quest). Items are put into your inventory and followers are displayed in the top left corner of the screen. Travel to the destination and talk to the main service provider there. They will take the item or follower, and, depending on whether or not you made it in time, they will pay you a small amount of gold.

These quests are a good way to quickly earn a small amount of gold, as you can do several of these in a few minutes.
You gain a little bit of experience for each completed quest. While of not much significance later, this can help you level up in the beginning of the game.
As you increase in level, the amount of gold and experience you get from completing these quests increases. However, it is still quite negligible compared to the amount received from completing many other quests and even raiding randomly generated dungeons found in the game.
Be careful when traveling at night. Enemies often sneak into the cities, and most stores and temples are closed after sunset anyway. Many different creatures besides rats and goblins will often lurk in cities, everything from humans, like Spellswords, to skeletons, lizard men, orcs, ghouls, and even zombies. But don't worry, it is very rare to encounter golems and such in town (and impossible before you reach the required level for encountering them as random opponents which is around 15).
To do a lot of these quickly, find a small village with a limited number of service providers. There is no need to speak to a villager to start the quest, simply make a tour of the pubs, and the quest will be activated when you speak to the right bartender.
If the destination for an escort quest is the Mages Guild, pick one of the doors, go in, and talk to the wizard. If he doesn't accept your follower and pay you, go back outside, enter one of the other doors, and try again. You may have to try every door into the Guild before you find the right one.

Rescue Quests
This type of quest is given by a king or queen of a city. It requires from the player to go to the dungeon and rescue a person somehow related to the king or queen (heir, son, daughter). The dungeons in this type of quest are one-leveled and feature a "boss" monster in the same room as the person who needs to be rescued.

Kill the Monster Quests
This type of quest is given by a king or queen of a city, who can be found in the palace. It requires the player to go to the dungeon and kill a high-leveled monster, usually for substantial reward. The dungeons in this type of quest are multilevel, and the game informs the player when the monster is near. The dungeon is named after the monster which needs to be killed.

Escort for a King or Queen Quests
This type of quest is given by a king or queen of a city. It requires from the player to escort a city ruler's relative to another city. You will be attacked by a rival faction (Mages Guild, Dark Brotherhood, possibly others) if you try to rest in a tavern.

Notes
Due to a bug in the game, you may encounter very hard monsters if you attempt the quests for rulers at lower levels and the enemy faction is The Thieves' Guild or a random noble.
The experience reward is 500 XP per level for palace quests and 50 XP per level for tavern quests.