Arbitrarily ordering records in a table
If I want to move record 0 to the start, I have to reorder every record

No, there's a simpler way.
update your_table
set order = -1 
where id = 0;


If I want to insert a new record in the middle, I have to reorder every record after it

That's true, unless you use a data type that supports &quot;between&quot; values. Float and numeric types allow you to update a value to, say, 2.5. But varchar(n) works, too.  (Think 'a', 'b', 'c'; then think 'ba', 'bb', 'bc'.)

If I want to remove a record, I have to reorder every record after it

No, there's a simpler way. Just delete the row. The remaining rows will still sort correctly.

It's easy to imagine a situations like:
Two records have the same order

A unique constraint can prevent that.

There are gaps in the order between records

Gaps have no effect on how a dbms sorts values in a column.

Some people have proposed using a decimal to store order, so that you can use &quot;2.5&quot; to insert a record in between the records at order 2 and 3. And while that helps a little, it's arguably even messier because you can end up with weird decimals (where do you stop? 2.75? 2.875? 2.8125?)

You don't stop until you have to. The dbms has no problem sorting values that have 2, 7, or 15 places after the decimal point.
I think your real problem is that you'd like to see values in sorted order as integers. You can do that.
create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);
    
insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will &quot;transform&quot; the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table