Chuck Miller in [Miller, Charles F., III On group-theoretic decision problems and their classification. Annals of Mathematics Studies, No. 68. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971] proves the following two rather nice and natural examples.
Theorem III.10. The free product of two free groups with finitely generated amalgamation can have unsolvable conjugacy problem. Further, the finitely presented HNN extension of a free group can have unsolvable conjugacy problem.
(Note that Miller calls HNN extensions 'Strong Britton extensions').
Now by Bass-Serre theory, there is a natural action of an amalgamated free product/HNN on the associated Bass-Serre tree, which should satisfy your "natural action" criterion.
Edit: The result mentioned by YCor can also be found in Miller's book.
Theorem III.23 The group $F_2 \times F_2$ has a finitely generated subgroup with undecidable conjugacy problem.
An important side remark, however, is that $F_2 \times F_2$ itself has decidable conjugacy problem, as do all RAAGs, in linear time. See [Crisp, John; Godelle, Eddy; Wiest, Bert; The conjugacy problem in subgroups of right-angled Artin groups. J. Topol. 2 (2009), no. 3, 442–460.].