There are some Challenge Quests that can be found in Ginza and Shinjuku.
"The Great Drunkenness:"
See the previous section.
"Heavy Weapon Recovery:"
For this, you need to head to Ikebukuro. There, go near the far eastern area that brings you to Shinjuku - you have to enter Ikebukuro, return to the highway, and then the overworld map. From there, run up and down along the wall to the northeast; there is a hole in it to the other side.
Head north to find a Domain at the Jujo Base. It's randomized, though... The boss, Grendel, is easily beaten. It has around 2,100 HP and the only real problem is a Physical and Gun resistance. After the Domain disappears, you'll get the SDF Equipment to deliver.
"RxW Smacktacular XIII:"
To begin, head to Shinjuku's underground. Exit it to the north of the Association room and, in that area, enter the room near the northwest corner. Within, opt to be in the show. Now you have to go around and kill hordes. An Apsaras Horde (weak: Fire) is to the southeast, near the entrance.
In the area to the north, you can find a Lorelei (weak: Fire) around the top-left corner. Go east an area to find Persephone (weak: Electric) along the northern street. Finally, go into the area east of the starting area to find a Silky (weak: Fire) in the southern alcove.
None of these enemies are really any threat to you at this point, hopefully, so there's no point in going into much further detail. After all of this, a final enemy, Tiamat, will appear. It absorbs Ice, nulls Fire, and is weak to Electric; it only has about 2,000 HP, so you'll be okay with a few Electric attacks on-hand.
"Serial Kidnapping + Arson:"
From Shinjuku's underground, go to the far west and far north, outside. Then head west an area from there and enter the southeastern room. Backtrack into the underground and head outside via the northeastern exit north of the Association.
Outside, to the northeast will be the Horde, laying in the intersection. This Wicker Horde is weak to Fire and only has around 1,600 HP - you can kill it in a single turn. Another will lie to the southeast, then another in the southwestern corner.
At that point, Cernunnos will arrive. This guy can use Megidola offensively to hit everyone for 100 damage or so. He will repel Electric moves, really resist Physical and Gun, and is weak to Force. He's still not much to deal with, having only 2,400 or HP, at this point...
"Prevent a Deal with an Overlord:"
Found this one on a New Game+. Anyways, head along to the Metropolitan Building - far west of the Shinjuku Association, then go north an area and west two. Head to the place where you met and probably fought Kuebiko in the lower west-central room.
Stop the ritual and you'll first fight three Anzu, who are weak to Force and drain Electric and have about 1,500 HP each. After is Astaroth. He likes to use party-wide attacks like Hades Blast (Physical) and Mabufudyne (Ice), so be ready with lots of Tetra-/Makarakarn. He also repels Ice.
After about 1,000 HP of damage, the Ring of Gaea woman will intervene with a Horde: Babylon's Might. In all honesty, one Titanomachia had them down. You then have to go find Astaroth again, found two areas back east. He has the same elemental resistances as before, but dies after about 8,000 HP of damage.