Avoiding Key Lookup when using MIN and MAX
I would rewrite the query like this:

SELECT
    sus.MaxOnlineUsers, -- Only select the most users
    sus.MaxOnlineDevices, -- Only select the most devices
    sus.SDHour, -- Used to allow creating the graph split into 5 minute increments
    sus.SDMinute, -- Used to allow creating the graph split into 5 minute increments
    s.Id AS SoftwareId,
    s.FriendlyName AS FriendlyName, -- Each software peice has a name
    s.MaxUsers AS MaximumSupportedUsers, -- Maximum supported users
    s.MaxDevices AS MaximumSupportedDevices -- Maximum supported devices
    -- DATEDIFF(SECOND, @dtStartDate, min(sus.SampleDate)) as OrderTime -- Used to sort
FROM dbo.Software AS s -- Get sw details
--Not used: LEFT JOIN dbo.SoftwareTypes AS st ON s.SoftwareTypesId = st.Id

--- Run this once for each software:
CROSS APPLY (
    SELECT x.SDHour, x.SDMinute, x.UserDivsor,
           MIN(x.SampleDate) AS OrderColummn,   --- Just order by this column
           MAX(x.OnlineUsers) AS MaxOnlineUsers,
           MAX(x.OnlineDevices) AS MaxOnlineDevices
    FROM dbo.SoftwareUserSamples AS x
    WHERE x.SoftwareId=s.Id
      AND x.SampleDate &gt; @dtStartDate -- Don't get all rows
      AND x.SampleDate &lt; @dtEndDate -- Don't get all rows
    GROUP BY x.SDHour, x.SDMinute, x.UserDivsor) AS sus

WHERE s.ClientId = @gClientID -- Multi tannancy 
  AND (@bFilterHiddenRows = 0 OR s.HideByDefault = 0) -- hide some rows

ORDER BY 
    sus.OrderColumn,    
    s.Id;


The CROSS APPLY construct lets SQL Server "loop" over each row in dbo.Software and for each query in that table, it runs an aggregate query on the much larger dbo.SoftwareUserSamples table, for which we'll optimize with the following index:

INDEX ON dbo.SoftwareUserSamples (SoftwareId, SampleDate, SDMinute, SDHour, UserDivsor)
    INCLUDE (OnlineUsers, OnlineDevices)


This should give you a nice, efficient seek (range scan, really) on (SoftwareId, SampleDate).

I removed the DATEDIFF expression and just sorted by the MIN(SampleDate) expression instead. It'll make your code a little more readable and perhaps even save you a few microseconds of CPU time. :)

Just crossing Ts and dotting Is, here's an index recommendation on dbo.Software as well, although I suspect this table doesn't really contain that many rows:

INDEX ON dbo.Software (ClientId, SoftwareTypesId)
    INCLUDE (Id, FriendlyName, HideByDefault, MaxUsers, MaxDevices)


A few best practices that I could gleam from your post:


Every table (with very few exceptions) should have a clustered index. It doesn't absolutely have to be unique if that's a problem.
Always prefix the table with the schema name.
Qualify all the column names with table aliases, so you can easily see which column belongs to which table.
If you're on SQL Server 2014/2016 Enterprise Edition or on 2016 SP1+, you should really try putting a columnstore index on the SoftwareUserSamples table for performance.