So I finally managed to defeat my first hard-world boss, the Destroyer. Actually, I did it twice, since the first time I killed him, he must have just been preparing to come around at me, because his head segment (and, therefore, the souls he drops) was nowhere in sight. I must have covered every inch for a screen in every direction, but couldn't find anything.
Did it without using the 'hot stone' exploit, although I did have a heart statue on a timer to help a little with the healing.
Had Adamantite/Mythril/Adamantite the first time, and a full Adamantite set the second. Used a combination of Night's Edge, a Clockwork Assault Rifle with crystal bullets and a Laser Rifle to slowly whittle him down.
Not sure where to go next. Probably the Twins.
edit: One thought occurs to me - it's a good thing that my house isn't Dwarf Fortress. My boss fighting arena is on the roof of my house, and each time I summon the Destroyer, he's killed every single one of my NPC's. If it were DF, no one would come back for years, if not decades at this point. Thankfully, it's not, so they start slowly respawning over the next couple of days. Kind of odd while they're all dead though, since my house goes all native - a combination of hallow and jungle critters all over the place.