Heiho,
Ich war wohl schon 3 bis 4 mal auf Rügen, das Bike immer dabei.
Der Ritt von Bingst durch den Buchenwald nach Sellin ist einer meiner Alltime-Favourites

(deutschlandweit), weil er Landschaft und Fahrspass so gut kombiniert. In der Granitz werdet ihr also sicher fündig.
Bei den Steinfeldern (Prora) kann man schön Schotter-Fahrtechnik üben.
Ob im Nationalpark Königsstuhl noch was geht, weiß ich nicht; da war ich 2004 zuletzt, und konnte mir den Küstenweg mit den Wanderern teilen. Da ist ja seitdem viel Küste ins Meer gestürzt...Den Wald im Hinterland hab ich auch als echt hübsch in Erinnerung, zumal sich auch einmal 10m vor mir ein kapitaler Hirsch auftauchte. Meine bisher einzige Begegnung in freier Wildbahn.
Generell ist der Osten interessanter, im Westen ist es einfach zu flach, und es wird eher eine Treckingrad-Tour (was auch seine Reize hat). Die ausgewiesenen Wanderwege durchs Landesinnere sind oft auch Wirtschaftswege;
Trails müsst ihr vor allem in Küstennähe suchen, da dort auch mehr Wanderer unterwegs sind. z.B gibt es ganz im Norden von Kap Arkona nach Westen an der Küste lang einen 5km langen Weg, der mit Rückenwind auch sehr viel Flow hat.
viel Spass euch,
komamati