I have a system where game objects can contain other game objects as their children, and have an update(float DeltaTime) function in my game objects which does the per-frame updates (ticks, or whatever your favorite engine calls it). I'm wondering whether it makes more sense to update child objects before their parents or the other way around - I want to have some relative update order determinism given that I specify that objects at the same level in the hierarchy are updated in no specific order relative to each other. Your $0.02 are welcome.

Pick one, make it a standard, and stick to it.

If you want more details, it depends on the nature of the parent-child relationship, really, and who talks to who more, and assumes the other will be updated first.

where children have their position and velocities relative to and dependant on the parent

I think that this is quite common, you often have an object attached to its parent (member->party, item->npc,guild->town) which acts depending on the state of the parent.

Best to encapsulate the control of the update in the object itself, a standard update method would look like this(pseudo code):
[source lang="java"]object::update()
{
// call internal update
this->internalUpdate();

for each child do
child.update();
end
}[/source]
When you wish to update an object class in an other way, just overwrite the update method like this:
[source lang="java"]SpecialOjbect::update()
{
// call super update
Object::update();

// do some post processing
...
}
[/source]

Dmytry, that's usually what I do in a clear owner->child type of a scenario, but it may not work in the aforementioned physics attachment system, since whatever function goes on updating all your objects would probably update the child already. Hence why i said, it depends on the nature of the relationship.

I have a system where game objects can contain other game objects as their children, and have an update(float DeltaTime) function in my game objects which does the per-frame updates (ticks, or whatever your favorite engine calls it). I'm wondering whether it makes more sense to update child objects before their parents or the other way around

I suggest to consider the idea of dropping extensive update process. I once read an article suggesting to not update at all.
I don't think that's feasible but I can sympathize with the concept and I worked out a system which is somewhat compliant with this concept. What I have done in my system is to have a single place when [font=courier new,courier,monospace]update(deltaTime)[/font] will be issued. There will only be one [font=courier new,courier,monospace]update [/font]call per tick. The user (script) is in charge of ensuring the information is propagated to the objects it needs, in any order it needs.
Exception are what I call live objects, similar in concept to the [color=#0000cd]volatile C keyword. So far those objects have the following properties:

1. They are architecturally simple. They don't have subcomponents and most cannot even be used as subcomponents albeit all can be instanced as objects in the script.
   
2. They are guaranteed to change atomically before each script is run and guaranteed to be consistent across different script invocations in the same tick.
   
3. They require (mostly) quite some work to be implemented in script.
   
4. They are typically backed by native data structures (some even take 0 bytes in script heap memory).
   

I have found myself pretty comfortable with this approach.

Now, in the case of "natively nested" components, such as the limbs of a ragdoll, you don't update them. They physics API updates them for you and pours out the transforms to your system. Albeit it appears reasonable the parent will be synced first, I specified no order is guaranteed.

So in short I suggest to consider not enforcing an order. But I'm interested in this discussion so please make specific examples. As I learned the hard way, nobody will get anywhere as long as generic objects are considered against arbitrary relationships.