What group-policies have you applied

Software installation policy is processed before Startup Scripts are executed. Sometimes that's exactly what you want, and other times it's not. You can't change it.

When I want a startup script to run before software installation I end up using group membership to control the execution of the startup script and I end the startup script with a command to add the computer to a second group that controls software installation. The only problem with this is that, to date, I have yet to find any reliable way to restart a Windows XP or newer OS from a startup script. (Yes, yes-- I've tried a variety of methods, too. I can discuss them in detail if you'd like.) As such, this always makes this strategy require two boots to "take effect".

You mention "preferences", so I think you're looking at doing things to the user's environment via a logon script. Logon scripts are executed, obviously, after logon. If you're looking to check to see if a piece of software has been installed during the logon script query the Windows Installer "database" in the registry to see if the program is there and "bail out". You'll find the installed products in the "HKEY_CLASSES_ROOT\Installer\Products" key. Obviously, you'll have to figure out the GUID for the package you're dealing with.

Edit: Group Policy client-side extension (CSE) processing order is performed based on the value of the GUID for the client-side extension, from what I've been able to glean from documentation. It looks like the CSE's with numerically higher GUIDs execute later. I don't have the GUID for the "Preferences" CSE handy so I can't tell you how it should act re: running before / after other CSE's.

On Windows XP, at least, dig into HKLM\Software\Microsoft\Windows NT\CurrentVersion\WinLogon\GPExtensions and look for the CSE for "Prefernces". REGEDIT will sort those GUIDs numerically, too, so you could be able to tell, visually, if that "Preferences" CSE is going to execute before/after other CSE's.

There isn't an out-of-the-box tool to do what you want, nor am I aware of any third-party tools that would help. I think you're probably stuck with manually building GPOs that contain all the settings you want.

Obviously, by combining all these settings together you're limiting your ability to be granular with applying only some of the settings in the GPO. I'd be sure you've thought your desired level of granularity through before you start with building-up the new GPOs.

Edit:

The desing trade-off in making GPOs is as such: Do you put a lot of settings into a single GPO, or spread the settings out over multiple GPOs. The advantage to a single GPO is quicker processing on the client (though on a LAN this won't be perceptible unless you have a LOT of GPOs) and less "stuff" to wade thru in the management interface.

If you pile everything into a few GPOs, however, you run the risk that later you may only want to apply a subset of the settings to a subset of computers or users. Software Installation policy has a mechanism to filter by security-group at a sub-GPO level, but for all other parts of a GPO there is no mechanism to selectively filter application at a sub-GPO level. You end up having to create "anti-GPOs" to "undo" the settings in the large monolithic GPOs, or you break the monolitic GPOs up, manually, into GPOs that you then filter by security group (or WMI filter, or by linking at different OUs).

It's probably not a big deal if you're not being very sophisticated with your use of Group Policy. I often have a "Domain-wide User and Computer Settings" GPO with very basic settings that I know will always apply universally. I'm careful, though, not to put settings in that GPO that might end up not needing to be universal later on, and create dedicated GPOs for those settings that I might want to toggle on/off for subsets of users or computers later.