it's a known 'problem' that the url's don't look as nice as it should. And at this time no solution is available. The biggest problem is that NextGen uses it's own router class (/lib/rewrite.php), which is required to show multiple pages within a plugin. This means that (no matter what) the base URL of the plugin is /nggallery/ and then a bunch of ugly stuff (from "/page-X/" to "/post/X/album-X/gallery-X/page-X/slideshow/").
At this moment I'm working on a new router class which fixes most problems (eg use the page/category/post name as base url) and let it use the same (permalink) settings as the WordPress installation itself, though it's more complex as it looks.
When as working version is ready I'll contact the NextGen developer(s) and post the fixes at these forums and maybe it will be included in one of the next versions.
Though, if you're a skilled PHP programmer and find a solution yourself, I'll be happy to use the fix ;)