help with levels

Hello,
Well my game been based on the book "Dune" is pretty bland with a lot of hills etc. I was wondering how would be the best like to make rock formations? which the player can walk on and they are able to be ver complex with tunnels etc in cases.

And does anyone know how a Dune could be made well with a height map? because they just don't have the right look to them, is it in the texture?

Thanks for any help.

Edward