Choose the correct tactic and the battle against the Covetous Demon is actually one of the easiest in the game. The trick is to position yourself to either side of the monster, ensuring you stand beyond its arm. Assuming this position means you move automatically when the Demon approaches you, and it can't face you because its arm remains in the way.
How to kill the Covetous Demon
After a while, the Demon will shift its weight over to the other side. As soon as this happens, either raise your shield or back away quickly to avoid the damage that's coming your way. That shift in weight indicates that the monster is about to roll towards you. Block it and you'll lose all your stamina, but if you take the damage to the face, you'll be in an awful lot of trouble.
Just keep attacking the enemy whenever you can, while leaving yourself with enough stamina to handle that offensive roll at all times. If you keep this strategy up, you'll actually take down this boss in very little time indeed.
How to find Mytha, the Baneful Queen
After you've killed the boss, go through the door that's over to one side, then head upstairs. Light the bonfire, then talk to Lucatiel to get your hands on the Ring of Steel Protection +1. Now go into the next room along, then head up the stairway over to your left. Kill the three enemies here, then grab the Radiant Lifegem from the far corner.
Keep going through the next door along, then head over the bridge. Stop when you come to the massive gear, then use it to dodge the archers' arrows while you kill the mage knight. When your opponent's dead, go into the next room along where you'll find a ladder to your left, and a hallway to your right.
"Set fire to the windmill with your torch as soon as you get close to it. Doing so drains all of the poison out of this area."
Enter the hallway on your right and pull the lever. Now go downstairs and kill the enemy that's lurking over to your right. As soon as you get to the next room along, take a left to loot a Pike from a chest. Once you've picked it up, go back into the room you left a moment ago and head towards the ladder. Two enemies will attack you as you approach it, so kill them before climbing up.
When you get to the top of the ladder, you'll have to kill an enemy. Now pass through the misty door and light the bonfire on the other side. Next, light up one of your torches, go back through the door, then head up the ramp on your right towards the windmill.
Remove the poison from the Mytha fight
Be very careful here so that you don't fall off, then set fire to the windmill with your torch as soon as you get close to it. Doing so drains all of the poison out of this area, and makes the next boss fight much easier as a result.
Make your way up the next set of stairs and take the Black Firebombs, but watch out for the nearby lever. If you step on it, you'll take a lot of damage from the darts that fly towards you. Ignore the ladder in the middle of this area, as well as the outside balcony for now, and instead go to the other side of the area. Here'll you find another enemy, as well as a Manikin Mask. Once you've killed the former and looted the latter, get out onto the balcony.
Where to find Laddersmith Gillian
Kill the enemy on the balcony, then smash the railing by the entrance and shimmy your way along the ledge on your left. Talk to Laddersmith Gilligan at the end of that ledge, and buy the ladder off him for 2,000 souls. That'll give you access to an area below that contains a Twinkling Titanite and a Pharros' Lockstone. You'll be able to find Gillian in Majula from now on, and he'll give you a ladder for the town well if you've not explored that area yet.
Make your way back to the balcony, then go all the way along to the end, beyond the wood railing. Cut it down and grab the nearby item to get a Simpleton's Spice. Pull the lever to raise a platform on your right, then take the newly-exposed Divine Blessing and a Soul of a Proud Knight. Just keep in mind that the platform won't stay elevated for long!
There's another bit of loot you can get using this platform too. Once you've pulled it and grabbed the two items, run out of the room before the platform comes back down. Pull the lever once more and get onto the platform before it can move again. This will take you up to a coffer. Loot it and you'll receive a Mirrah Shield.
Jump down and then climb up the ladder that's by the platform. Now make your way along the hallway towards the right. Talk to the man who's in the room beneath you, then go back up to the main hallway and kill the mage knight further along. Again, watch out for the poison pots nearby.
"There's a coffer full of poison here, but it also contains a Pharros' Lockstone, so loot it and repair the damage before moving on."
Carry on up the stairs to your left, then kill the pair of pyromancers and the mage knight when you reach the top. There's a coffer full of poison here, but it also contains a Pharros' Lockstone, so loot it and repair the damage before moving on.
Go back downstairs and then carry straight on ahead until you come to another pyromancer. Kill it using a ranged attack, then get ready to make a pretty challenging leap over to the other part of the platform. Just make sure you jump across at the very last moment, and aim for a landing spot on the left-hand side.
Grab the item at the end of this platform to add a Radiant Lifegem to your stash, then take a Crimson Water and a Soul of a Brave Warrior from the coffer. Before you head back, there's another item waiting for you on the bridge beneath you.
Fall straight down from the position where the last item was located. Grab the new item to add a Human Effigy and a Poison Broadsword to your inventory. Now jump over to the platform by the wall, head left, then go upstairs to get back to the floor you were on a few moments ago.
Go back to the room that leads to the balcony, then climb up the ladder. Go into the hallway on your left, then carry on up the stairs. Kill the mage knight and the pyromancers at the top of the stairs, but watch out for the poisonous pots by the pyromancers. Once they're all dead, make your way around the corner, then go upstairs and kill the next pyromancer you come to.
There are two mage knights guarding a door on the other side of this next room. They're blocking your path to the next boss, but ignore them for now and instead take the stairs near the middle of the room. Smash up the pots on your right, but do so at maximum range so you're not infected with the poison they contain.
Just behind those broken pots is a pack of poisonous bugs. Kill them before they can attack you as a collective, otherwise you'll suffer a great deal of damage from their poisonous gas attacks. Grab the Smooth & Silky Stone from the corner, then attack - not open - the chest to get a Work Hook and a set of Dark Gauntlets.
How to find Mytha, the Baneful Queen
Don't use a Pharros' Lockstone on the face up the stairs - just leave the room. Now go up the next set of stairs along to kill the Invader, and loot Brigand Gauntlets +5 for doing so. When you get to the end of the next hallway along, interact with the wall on your right. Don't worry about not seeing any on-screen indicators, just interact with it as though there was an item to collect.
Doing so will reveal a hidden wall. Behind it is a bonfire you can light. Now go to the other side of the room and again interact with the wall. Go behind the next hidden wall and you'll be able to loot a Petrified Something from the chest.
When you've finished looting everything, make your way back downstairs and kill the two mage knights who are guarding the path to the boss. Grab the Poison Stone from the corner, then go upstairs and pass through the misty door to start the fight against Mytha, the Baneful Queen, the Baneful Queen.