I'm playing the free Daggerfall EN Setup version of Daggerfall, not the GOG version (even though I have it too).

I'm out of the starting dungeon, I have joined Mage's Guild and even finished one quest for them, and received the first main campaign letter and met the lady, yadda yadda.

Now I am at the Daggerfall castle, and the queen won't give me a quest as I am at a level too low (2). I presume it is one of the main campaign quests. However, the king is ready to give me some random quest in the meantime, but they seem... odd. They seem simple enough, but for a reason or another I am unable to finish the quests. Two recent examples (from the king):

1. In one quest I was supposed to bring a gem or somesuch to some lady in certain inn, and she will tell me what to do next. Ok, I give her the gem, she gives me some other item back and tells me to bring it to B. The problem is, the second part of the quest is not recorded to my quest log, but the original one given by the king has been erased (I presume that is because I completed that part of the quest).

Since I didn't write down to whom and where I should bring the second item, I'm at loss what to do next. So I gave up, and reloaded the game so that the king would give me some other quest instead. Is it normal that part of the quest is not recorded to a log, and I should write down myself conversations and details just in case?

2. The next quest was about bringing some item to some lady in her residence in another town. I find that residence quite easily by asking the town people, it is marked in my town map... but inside the residence, I see no such lady. In one of the rooms of the residence there is some man but when I ask him about the lady, he knows nothing.

If I go back outside to ask NPCs about the lady again, they just point me back to her residence, where that man is. What gives? Is this quest also bugged, or is there something I'm still supposed to do or figure out? Like that man has killed the lady and blaa blaa blaa, but then I have no idea what to do next. I tried attacking him, but he seems to be an NPC that can't be fought, he doesn't care of any attacks. Or is the lady in her residence only at certain times of the day, or what?

If these random quests are that broken in the supposedly fixed Daggerfall version, this doesn't bode well for me ever finishing this game. The Mage Guild quest worked though, I was supposed to kill some baddie in another Mage Guild, and yeah when I walked around in that mage guild in another town for awhile, some baddie appeared and attacked me there. I could kill him/her and I got a reward when I went back to the mage guild that gave the quest.

I'm not sure about the first point (journal), but I'm certain that I've always managed to find people supposed to be in residences. Please check again: Have you been in all rooms? Have you climbed up all ladders in the house? The ladders are easy to miss.
I suppose my journal did contain the important information - otherwise I would have been lost in most quests.
For the next stage in the main quest, you need to be level 3, if I remember correctly.

Thanks, that was it. ;) There was indeed a ladder on the wall of one of the small empty rooms (which was more like a closet), and clicking on that ladder brought you to the attic where the lady in green was. The ladder was a bit hard to discern from the wall as it was the same color.

That seems to be some generic subquest though because when I asked the same king for the next quest, I was supposed to bring some shirt to some lady, and it was a carbon copy of that mission, only the item and the town were different. The residence had exactly the same ground plan, and there was that same (looking) man in one of the rooms, and the lady in green in the attic.

Meh. I joined the Fighter Guild so that I can do some killing quests with my Spellsword instead (already are in the Mage guild).

You're right that a lot in Daggerfall has been built from a limited set of building blocks, including the dungeons. Luckily, the guilds and temples offer quite diverse quests, and there are the 20 main quests, which all require you to visit hand-designed dungeons (with level requirements growing from 3 to 14).
Have fun!