After combining pieces from all the above links, I came up with this script, simplified for the sake of the answer.
Tables Before Changes
JOB
Id Guid PK
Name nvarchar
CreationDate datetime
REPORT
Id Guid PK
JobId int
Name nvarchar
CreationDate datetime
SCRIPT
-- Create new Job table with new Id column
select JobId = IDENTITY(INT, 1, 1), Job.*
into Job2
from Job
order by CreationDate
-- Add new JobId column to Report
alter table Report add JobId2 int
-- Populate new JobId column
update Report
set Report.JobId2 = Job2.JobId
from Job2
where Report.JobId = Job2.Id
-- Delete Old Id
ALTER TABLE Job2 DROP COLUMN Id
-- Delete Relationships
ALTER TABLE Report DROP CONSTRAINT [FK_Report_Job]
ALTER TABLE Job DROP CONSTRAINT PK_Job
-- Create Relationships
ALTER TABLE [dbo].[Job2] ADD CONSTRAINT [PK_Job] PRIMARY KEY CLUSTERED
([JobId] ASC)
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 90) ON [PRIMARY]
ALTER TABLE [dbo].[Report] WITH CHECK ADD CONSTRAINT [FK_Report_Job] FOREIGN KEY([JobId2])
REFERENCES [dbo].[Job2] ([JobId])
ON DELETE CASCADE
ALTER TABLE [dbo].[Report] CHECK CONSTRAINT [FK_Report_Job]
-- Rename Columns
sp_RENAME 'Report.JobId', 'OldJobId' , 'COLUMN'
sp_RENAME 'Report.JobId2', 'JobId' , 'COLUMN'
-- Rename Tables
sp_rename Job, Job_Old
sp_rename Job2, Job
I created the Job2 table because it means I didn't have to touch the original Job table (apart from deleting the relationships), so that everything could easily be put back to it's original state in case something went bad.