R.B.
Yeah ideally you'd like to solve your problem by setting up constraints to guide the tools, because your floorplanning work is more likely to be wasted if your design changes significantly enough (though creating relative placement macros for sub blocks of your design can help preserve your work). Area constraints, as opposed to timing constraints, can be helpful in nudging the tools to placing smarter.
Of course, like you said, the tools might not have enough smarts to do what you want or it might take too long to place/route without some intervention.
As far as floorplanning, the main thing is is to understand the layout of the routing resources in your target FPGA. Xilinx's Spartan-III, for example, has direct lines (that connect adjacent CLBs), double lines (that connect every other), hex lines (which don't connect every 6 but every 3), and long lines (which do connect every 6). So from best to least, you want logic in: 1) the same CLB, 2) adjecent CLB, 3) two CLBs away, 4) three CLBs away, or 5) six CLBs away. Four and five CLBs away could be worse than six.
A lot of times I find that when I floorplan I'm fixing some crazy things the tools have done. Like for some reason the tools will take a 32-bit register and instead of keeping it in order, it'll mix it up in a seemingly random fashion.
They seemed to have architected their FPGAs for data to flow horizontally, so keep that in mind. I'm not sure if it matters, but I always go left-to-right because it feels natural.
Heh sorry I don't have too many pointers. I try not to floorplan (unless I want to veg out. I find Xilinx's Floorplanner relaxing, it uses pretty colors) and it feels more like an intuitive art than a science. One thing you can try is to compile your design with only the difficult logic and the other logic removed. This will help speed up the floorplan-route-results cycle which sometimes can be more productive than trying to plan everything up front, especially when we don't have a good knowledge of the routing or we have the wrong ideas.
Best of luck, Vinh