You most probably have a database model problem and possible index problems as well.
First off, are you using composite keys? If, why is it "seller, category"?
If you add a composite key that is: "category, seller" and then update your query to equal this:
$sql = "SELECT * FROM items WHERE category = '21' AND seller<>'johndoe' LIMIT 100";
I am certain you will get a massive speed increase, since now we first limit the query to any records in category 21 that is not made by seller johndoe, instead of limiting the query to any records not made by seller johndoe that is also in category 21.
However, the problem you will see when this works is that you will always pull the same 100 records (unless some is deleted) i.e. ASC order. In addition the RAND() function in SQL should be avoided like the plague since it quite honestly is a "DB killer" on larger tables.
Instead what you can do is this:
$range_from = mt_rand(1,$total)
$sql = "SELECT * FROM items WHERE category = '21' AND seller<>'johndoe' LIMIT $range_from, 100";
However, please note that LIMIT X,Y is also very slow. The reason for this is due to if you have a table with a million records and write: LIMIT 997000, 100 the SQL engine actually read all 997000 records to get to the ones you want to pull. This means if you want to speed this up more than the suggested query above, you need to alter your database models with this in mind, allowing you to base queries on primary keys, and being certain that you can actually use it internally in the software after.