握り飯の初出は、『常陸国風土記』です

好きなおにぎりの具ランキング　3位「ツナマヨ」、2位「明太子」、1位は？
https://news.mixi.jp/view_news.pl?media_id=40&from=diary&id=7462613

風土記は、元明天皇の詔によって編纂が命じられた、「古老（ふるおきな）の相伝ふる旧聞（ふること）を申す事」を聞き取ったものです。ということは、他と区別された特産、特筆性のある食い物だと想像できます。
そこに、
「風俗說云二握飯筑波之國一」とあります。
（一点をずらして、「風俗說云二握飯一筑波之國」（握り飯と風俗の言葉に云うは、筑波の國なり）と読みたいところです。それとも、こう打つ必然性があるのか…）
ということは、普通のごはんと区別されていた存在だったということです。

ご飯は平安時代『類聚雑要抄』などにあるように、
https://shoryobu.kunaicho.go.jp/Toshoryo/Viewer/1000555960001/110934a0cc2c482f93f934b2ec8bbf25
（７P〜８P）
器に一口ずつ盛り上げられて食べられました。（「飯一口　在蓋」ここに記載されているには蓋つきの銀の器です）この７Ｐにあるアワビ、タコ、コイ、鯛など他のおかずは、つまみであり、飯のタネです。これをみると、たとえば肉じゃがや餃子が、おかずにもなるし酒のつまみにもなる…というのは、日本の伝統なのですね。
私は無窮会版を整理したことがあります。
無窮会https://ja.wikipedia.org/wiki/%E7%84%A1%E7%AA%AE%E4%BC%9A
しかし、ネットで公開していませんので、上は、宮内庁書陵部の史料です。

さて、それを包んでおにぎりが出来ました。『常陸国風土記』の影響を受けたのかそうでないかはわかりません。
『類聚名物考』という別の書物には、木型で打ち抜くとあります。
ということは、お握りそのものです。
現代でもお握りのコツは、握らずにまとめることです。
それを笹などにくるんだり表面を焼いたりするのですが、おかずはというと、上の宮内庁書陵部の史料の７Pにあるような、当時のおかずでしょう。
だから、おそらく早かったのは、サバのひしお、ネギ味噌です。
『大宝令』にはすでに「美噌」や「未醤」という表現があります。古代からのおかずです。ネギは、禰木という表現が上代からあります。もしかしたら、『日本書紀』にあり、記紀の仁徳天皇の歌として「於朋泥」（おほね）として読まれている大根のみそ漬けかもしれません。

そういう由来を考えると、
サケなどと並んで、シーチキンやコーンのマヨネーズ和え、スパムなどがあるのは、当然のことです。
ありあわせのつまみ兼総菜を、木型で打ち抜いて表面を焼いた飯に添えたのが始まりですから。

山椒の葉の煮つけや、大葉味噌（クルミなどを入れる）に心惹かれる気持ちはありますが、本家本元争いをすることもないでしょう。