Yes, you do understand correctly what those sentences mean.
In the Slavic languages in general and in Polish in particular, the direct object of a verb is in the Accusative case when the verb is affirmative, but if the verb is negated, the direct object is in the Genitive case (see #3 here). It is one of the most basic rules of Polish syntax and case usage....
I don't understand either grammatically or morally, how is "brother" an instrument with which the subject goes on a walk.
You are right, brother is not an instrument here. "I go with my brother" — this type of relation is called comitative semantic relation.
Morphologically, it behaves like Instrumental case, but functionally it serves a ...
The preposition z meaning 'with' takes the instrumental case, is all. E.g.
Mieszkam w domu z ogrodem
The instrumental case is used to indicate the instrument/object with which an action or state of being is performed.
...which is true, but that's not the only use of the instrumental.
Of tools, instruments, and modes of travel
After the ...