You mention a different backpack. If you haven't looked around for that, I'd make that a priority. To to an outdoors shop, get something proper.
I daily use a Deuter AC Lite 16. It has no special compartment for laptops, bit my 14 inch just fits in a tight elastic near the back. For a bigger laptop, I'd place a hoodie in the bottom.
It's a small hiking backpack, and it's curved back sits extremely well, I think. It's great for biking, too.