iPhone / iPod / iPad Sync Problems
You might have an old version of iTunes which does not support folders. The current version is 10.0.1 so I would highly recommend upgrading. If you have the latest then try to reinstall it. This should fix your app/playlist issues.

As for the applications being randomly added ... uncheck the "Automatically sync new apps" box if it is checked. If it is already unchecked, then hopefully reinstalling iTunes will fix this too.