The question is: why are noun and verb phrases the basic building blocks of all grammar?
Candidate answer: cognitively, we perceive the world as objects and relationships between objects. Thus, nouns reference objects and verbs reference relationships.
I'm not sure how widely accepted her work is, but Ljiljana Progovac argues that the distinction between objects and predicates predates the development of recursive syntax. At some earlier stage, according to her theory, syntax was limited to what she calls a two-slot grammar, which combines single objects with single predicates; we see remnants of this in compounds like kill-joy and turn-table, which she claims appear across a wide variety of different languages and make no distinction between agents and patients (turn-table vs turn-coat, tumble-weed vs tumble-dung).
If her theory is correct, then yes—the most fundamental distinction, predating recursive syntax and various other things that appear in all modern languages, is between objects and predicates (or "relationships" as you call them, though I'm not sure I'd describe "is cold" or "falls" as a relationship). This distinction might be innate, or might be learned, but does seem to be universal.
Your cognitive focus fits well with Langacker who defines these basic grammatical categories semantically, invoking cognitive abilities such as "conceptual grouping, tracking relations through time, [and] focusing of attention" (2009: 174):
Counter to received wisdom, I claim that basic grammatical categories such as noun, verb, adjective, and adverb are semantically definable. The entities referred to as nouns, verbs, etc. are symbolic units, each with a semantic and a phonological pole, but it is the former that determines the categorization. All members of a given class share fundamental semantic properties, and their semantic poles thus instantiate a single abstract schema subject to reasonably explicit characterization. (Langacker 1987: 189)
So how does Langacker characterize nouns and verbs? Hollmann (2013: 278) gives the following summary:
Langacker [...] define[s] nouns and verbs as profiling THINGS and PROCESSES, respectively. A THING, in this technical sense, is characterised as “a region in some domain” (Langacker 1987a: 189), or, without the spatial metaphor, as “any product of grouping and reification” (2008a: 105). A PROCESS, by contrast, is a relation between entities which develops and is followed through time (see Langacker 1987a: 248).
For Langacker, this approach complements the Radical Construction Grammar (Croft 2001) bottom-up view of labels such as 'noun' and 'verb' as "metageneralizations over construction-specific categories" (Goldberg 2006: 221):
I recognize both the validity and the relevance of this bottom-up approach, which offers a way to accommodate the linguistic importance of these elemental grammatical notions while maintaining the firm basis of observed distribution. This is not at all inconsistent with my top-down characterization in terms of basic mental operations. Though speculative, I would argue that these characterizations are plausible from both the cognitive and the linguistic standpoint. I suggest, moreover, that they (or something comparable) are needed in a full account. They play a role in explaining why the distributional patterns supporting the metageneralizations [...] should be observed in the first place. I view the mental operations in question as being inherent in the conceptual archetypes and aspects of clausal organization which anchor the target categories, and thus as being responsible for their emergence. (Langacker 2009: 173-174)
