My concern now is that I might lose some of the comments already on my blog if I change the number of nested levels... Do you know if they'd be deleted or become invisible if I make the change?
Nah, I tested it with my blog and it only affects new comments.
It looks like the comments might nest better if you could just reduce the indent... have you tried mucking about with the code in comments.php?
I'm using Mystique as my theme and while I don't get a lot of comments, when I was testing how they looked they worked okay. Not sure if you need a plug-in or to just borrow a bit of that theme's code?
The shitty thing about Wordpress is that if you want a free account, you can't modify the theme layouts at all. You can choose how deep nested comments will go, but the indent is beyond what you can do. You'll need to upgrade your account for that.