TL;DR

SQL Serverでは、テーブルに主キーが未設定かつトランザクション分離レベルが「SERIALIZABLE」な場合に、テーブルに排他（X）ロックがかかる
それとインテント排他（IX）ロックが衝突することで、同一行の更新処理だけでもデッドロックが発生する

検証環境

SQL Server 2016 Standard（たぶん他のバージョンでも再現可能）
対象のテーブルは下記定義のもの。key1（大分類）とkey2（中分類）を指定して値を取り出すイメージ

test_table.sql

CREATE TABLE test_table (
    key1 CHAR(4),
    key2 CHAR(4),
    value VARCHAR(255)
)

test_tableの主キーは未設定

デッドロックが発生するクエリ

test_tableのkey1, key2を指定して特定行の値を更新するクエリを同時に2つ実行する。
ポイントはトランザクション分離レベルを「SERIALIZABLE」に設定している点。

transaction1.sql

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
-- デッドロックを起こすため、同じクエリを無限ループする
WHILE 1 = 1
BEGIN
    UPDATE test_table SET value = 'transaction1' WHERE key1 = 'foo1' AND key2 = 'bar1'
END

transaction2.sql

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
-- デッドロックを起こすため、同じクエリを無限ループする
WHILE 1 = 1
BEGIN
    UPDATE test_table SET value = 'transaction2' WHERE key1 = 'foo1' AND key2 = 'bar1'
END

この2つのクエリをSQL Server Management Studio等で実行すると、数秒でデッドロックが発生する。

なぜ同一行の更新だけなのにデッドロック？

SQL Server 2012以降では、拡張イベントのsystem_healthからデッドロック情報を調査できる。

SQL Server 2012 のデッドロック情報の取得について at SE の雑記

SQL Profilerを起動してトレースを始めてから事象を再現して……と手順を踏むより遥かに簡単だ。良い時代になったものだ。

xml_deadlock_reportを確認すると、2つのプロセスがオブジェクトのIX（インテント排他）ロックを取得したが、X（排他）ロックを取得できずにデッドロックに陥ったことが分かる。
これを見て「あ～なるほどね～」となった貴方はSQL Serverチョットデキル人。（私を含む）そうでない人は下記の解説へGO。

そもそも「インテント排他（IX）ロック」とは

インテントロックとは？ - Microsoft SQL Server Japan Support Team Blog

では、テーブル A に S ロックが獲得されている時に、テーブル A に属する行 B に X ロックを獲得させないようにするためにはどうすればいいでしょうか？
それを実現するためには、行 B がテーブル A に属していることを知っているロックの要求元が、行 B に X ロックを要求する前に、テーブル A にロックを獲得して、テーブル A に対して他のロックが獲得されないようにすることが必要です。

テーブル全体の共有（S）ロックを取得中に別のプロセスが特定行を更新すると、テーブルの内容が変わってしまって困るため、インテント排他（IX）ロックという仕組みが存在する。
今回の例では、test_tableの特定行を更新する前に、test_tableのIXロックが取得される。

なお、IXロックとIXロックは互換性がある（複数トランザクションで同時に獲得できる）が、IXロックが取得されているオブジェクトに対して、別トランザクションから排他（X）ロックを取得することはできない。

SQL Server トランザクションのロックおよび行のバージョン管理ガイド - SQL Server

テーブルの排他（X）ロックを要求した原因

素直に考えると、1行の更新だけであれば行ロックで事足りそうに思えるが、上記の例ではテーブル全体のロックが要求される。
これには2つの原因がある。

テーブルに主キーが設定されていない
トランザクション分離レベルが「SERIALIZABLE」に設定されている

テーブルに主キーが設定されていない

デッドロックが発生するクエリのUPDATE文だけをSQL Server Management Studioに貼り付け、「実際の実行プランを含める」にチェックを入れた状態でクエリを実行すると、table scanが発生することが分かる。
ここで発生するtable scanとトランザクション分離レベルの組み合わせにより、テーブルのXロックが要求されることになる。
（ちなみに、test_tableに適切な主キーを設定するとindex scanになる）

トランザクション分離レベルが「SERIALIZABLE」に設定されている

トランザクション分離レベルの基礎については下記の記事が参考になる。
【SQL server】トランザクション分離レベルについて - 小物SEのメモ帳

「SERIALIZABLE」を指定した場合、ファントムリード（トランザクション中に同一テーブルを複数回読み込んだ際、レコードが増える現象）を回避するため、参照中の範囲に範囲ロックをかけて別トランザクションからのレコード追加を防いでいる。

SET TRANSACTION ISOLATION LEVEL (Transact-SQL) - SQL Server | Microsoft Docs

トランザクションで実行される各ステートメントの検索条件に一致するキー値の範囲には、範囲ロックが設定されます。これにより、現在のトランザクションで実行されるステートメントの処理対象となる行はブロックされ、他のトランザクションによる行の更新や挿入ができなくなります。

よって、

主キーが設定されていないことでtable scanが発生→テーブル全体が参照範囲になる
そのため、範囲ロックはテーブル全体となり、テーブルのXロックが要求される

という動作になる。

デッドロック発生までの流れ

ここまで解説すれば、先程のデッドロックについて説明できる。

transaction1がtest_tableのIXロックを取得する
transaction2がtest_tableのIXロックを取得する（インテントロックの互換性により取得可能）
transaction1がtest_tableのXロックを取得しようとするが、transaction2のIXロックの存在によりロック待ちとなる
transaction2がtest_tableのXロックを取得しようとするが、transaction1のIXロックの存在によりロック待ちとなる

こうして、1行だけの更新処理でデッドロックが発生する。

回避方法

前述の通り、主キーが未設定かつトランザクション分離レベルがSERIALIZABLEな場合のみtest_tableのXロックが要求される。
よって、デッドロックを回避するためには下記のいずれかを行えば良い。

test_tableに主キーを設定する
トランザクション分離レベルをSERIALIZABLE以外（READ COMMITTED等）に設定する

まとめ

デッドロックといえば2テーブルのロック順序の違いにより発生、みたいな認識では不十分。
たった1行の更新でもデッドロックが発生する可能性はある。

参考

SQL Server 2012 のデッドロック情報の取得について at SE の雑記
インテントロックとは？ - Microsoft SQL Server Japan Support Team Blog
SQL Server トランザクションのロックおよび行のバージョン管理ガイド - SQL Server
【SQL server】トランザクション分離レベルについて - 小物SEのメモ帳
SET TRANSACTION ISOLATION LEVEL (Transact-SQL) - SQL Server | Microsoft Docs
Lock Escalations in the Isolation Level SERIALIZABLE | 　※Lock Escalationの発生に関する記事だが、調査の上で大変参考になった

【SQL Server】1テーブル・1行の更新だけでもデッドロックが発生するという話