Just did one of the bosses on my first attempt, and without looking at any guides, sooo impressed with myself right now :)

I had a long play session last night, explored the Bastille from top to bottom. I've got 4 different ways to go atm but stupidly (I guess) chose the Belfry first. There dark souls showed it's annoying antics again. I was just taking a sneak peek before going back to spend my hard earned 62k souls when I get invaded while hollow. Not wanting to waste my time on that and risk my bounty, I sign out of psn, banishing the invader. (And unlike Dark souls, it doesn't quit you back to the title screen, you can keep playing).

5 seconds later the invasion message pops up again for an AI character. OK I'll just leave, nope exit closed. Homeward bone doesn't work, quit game disabled. Ok, so you want to be smart with me... I wait until the little save game flame has come and gone and I hard quit the game. Restarted the game. It accuses me of not closing the game properly but loads no problem, exit is open, so I leave, fast travel to Majula, spend souls, and back again.

Back in the belfry, same thing happens. Invaded again (still in offline mode and hollow). I look for the invader. Find him on the top with 5 more dwarfs with cross bows taking pot shots at me, while my spells are very ineffective. I try to take them on, but the delay for casting is enough already to get killed.

Second attempt, I run around, let them trail me around corners so I can pick up the loot, pull the level (bell rings) and loot a chest. That last animation takes too long and just after I pick up the items I get hit with 3 or 4 crossbow bolts, dead.

Third attempt, the gate to the mist is open. I'll go that way instead. I run into a bunch or Gargoyles... Well that's in a different league of difficulty compared to the bosses so far. I hold out for a bit, deal some damage while dodging three at a time, until 1 decides to go high and blast me with fire from above, 1 hit death. Guess I'll need some help there, although that means going online and having to do pvp most likely, bah.

Or I could first go to No man's wharf, Exile holding cells, or whatever that huge blue fort is you reach from Sinner's rise. Where should I go first.

Sinner's Rise has a very difficult boss (which is one of the main bosses at the same time), so I suggest you leaving that for later. Especially since the boss is very far away from the only bonfire in that area, not mentioning that you need the key from the area after the Gargoyles to make that battle manageable (a.k.a - with a bit of light, since it will be pitch dark otherwise).

Gargoyles, I suggest you bringing your best 100% Damage Reduction shield with at least 60% Stamina reduction. That's for melee builds. Dodging is worthless, keep shields up at all time and try to isolate a single gargoyle until it's HP is critical. When it starts its fire routine, focus on another and put that one on critc HP as well. Try to down both at the same time and you'll have at least 30 seconds with a solo gargoyle. That'll make the battle manageable.

If you don't want to go there, then if you've got a fragant branch of yore, you could go to that tower with the petrified woman on Majula and unpetrifiy her. That'll unlock the next area, Shaded Woods, which is a bit more manageable. Or try your luck on Huntsman Copse after Heide's Tower of Flame.

Out of the six bosses i did this happened with two. This was for the heides tower boss and theno mans wharf boss. Compared to other bosses they take a different set of skill which explains it. Though compared to my usual self i was very patient and concentrated in one of those fights i got hit zero times. 

As letsatdark said nomanswharf and huntsman corpse should be very easy for you since you just finished the lost bastille. Also you can buy a ring from a cat that lets you survive big falls, just outside of her house their is a well traverse down their for some items and a new area! 

Ok blue castle is out for now, and indeed there are tons of locked doors down there, guess I need to key first anyway. Gargoyles look to be a waste of effigies for now. I don't have a lot of damage reduction, caster build, dodging is all I have... I'll check if I can even hold a heavy shield. No branches of yore yet. I guess I'll check down that elevator in the Exile holding cells, and explore No man's wharf first.

Grave of Saints and The Gutter might be a bit too much for him right now, if he's having difficulties with the Gargoyles. Even if he's playing offline, thus not being constantly invaded by the Rat Covenant on Grave of Saints, the boss there is a megamix version of the gargoyles with the bajillion rats in that extremely small area. 

The Gutter....let's just say it makes Blighttown descent look a kindergarden child's play in comparison to how it is. First area in the whole game an enemy oneshotted me, even with 600 armor back then. Heck, I have 950 armor with the Ring of Steel Protection and most enemies can two shot me there. Not to mention the constant darkness and endless falls and floorboards breaking

I bought that ring, used an effigy to get full health, and still splattted on the first landing hehe.
Maybe my max health is high enough now to try again, thanks for the reminder!

Your first branch will be either on Sinner's or Haverst Valley then. No Man's Wharf is a easy area, especially if you have a Pharros Lockstone to use the contraption in the middle of the area to lighten up the majority of the place. It won't take you anywhere new afterwards, but it's a good place to farm souls at least. 

Be mindful of the oil throwing enemies there though. If you're reliant on Fire spells, you'll set yourself on fire. Also most enemy archers use Fire arrows there too to set you on fire if you've got oil on yourself. 

Caster builds will have a bit more difficulty on Gargoyles then. Keep always away from them and bring lots of casts. You're gonna fight through 6 gargoyles so you'll need most of the spells available to you. If that's still not enough, I guess co-op it's the only way to go. Try to bring someone that's melee oriented, because you'll need a tank more than anything.

I realize I'm still only at the start of the game, which is awesome :)

No pyromancy glove yet, I just levelled enough to be able to use lightning spear. I've got socerer's staff+5 with 15 great soul arrows, 60 regular ones (not very effective against bosses). Priest talisman +1, 11 lightning spears and 4 lightning storms (not all that useful either). Fire sword +2 and straight sword +2. Int faith and atn are all high (22,22,25), vigor, end, vit are lacking. Well all the other stats are 12 or lower. I had expected to find better spells by now, but so far it seems I've wasted souls upgrading int. And I really need to find some more tritanite, small and large. Seems very rare so far. I wasted it on a dagger and a robe I no longer use :/

I just used my 3rd Pharros lock stone in the bastille, guess I'll find one again for the wharf. Btw is there a place to unload all the junk I don't need?