You should be able to go into the underworld right now. Look above the twilight missions and there ought to be another icon there...
Graces are really a mixed bag. If you go for a "mutt" build, you'll wind up with high life (using the yakasani magatama) but you miss out on some stellar damage stacks.
One thing I can recommend is getting that AA toughness using a max stamina scroll - they hit really hard in the underworld, but you also get lapis lazuli - collect enough and there's a merchant at the entrance that lets you upgrade the level of + drops, % of ethereal that drops etc, and it carries over into the main game.
I'm actually progressing now, but man, the next boss I have to get through is Tate Eboshi, and I royally hate that fight. Vanilla Tate in the main game is annoying, x that by 12 in the underworld, then double that in the depths.
But the depths shift every day for a new mission, so I may just wait.
I have a solid Onmyo warrior set now, good untouched magic and doing massive purity damage with the phoenix wing. Every onmyo shot that connects gives me about 20% anima, so spamming yokai abilities too. And it's still brutal
The scrolls you collect will make a massive difference in survivability. Highly recommended
edit: It seems to me the underworld starts at 750ish and just gets harder. Some of the levels are so much worse than the boss at the end lol....