I think the question is too broad. There are a variety of such examples, and it seems that many combinatorial items and computational complexity items would fit the bill. The OEIS has a "most wanted" list, and so do I, but it is not clear which of these are a best fit for your question.
I start with http://oeis.org/A051236 which relates to the determinant spectrum problem mentioned by Will Orrick in https://mathoverflow.net/a/21510. Even conjectured values are known only for the first twenty or so terms. There are many related sequences, including http://oeis.org/A003432, the maximal determinant of an order n real 0-1 matrix. These are computationally challenging because we only know what such a matrix looks like for some n. We do not understand the determinant function as a combinatiorial entity enough to predict its range on certain sets.
Ramsey numbers provide several easily estimated and computationally hard sequences. I'll let an expert expound on these.
http://oeis.org/A005245 is another favorite of mine relating to integer complexity. Harry Altman has studied this, and posted on MathOverflow about it. Many terms can be computed now, but since for each n it involves a minimum over exponentially many configurations, one has to be clever in how to compute it. It is less challenging than computing Ramsey numbers, but you can't analyze it and compute bits of it like you can a Fibonacci sequence.
There is Dedekind's problem, http://oeis.org/A000372, or for universal algebraists, the size of the free distributive lattice generated by n elements. In fact, free spectra and enumeration of structures satisfying certain not necessarily equationally expressed conditions are subjects of ongoing research. Union closed families fall under http://oeis.org/A102897, and are another personal favorite.
Under suitable encoding/listings, various sequences of 0's and 1's are of interest. These are languages of varying computational complexity, usually corresponding to whether the nth structure of a list has property P or not, for example if a given graph has a Hamiltonian cycle.
I think all of these examples and many more fit your criteria. You might consider revising your question to give more examples and nonexamples from the OEIS corpus.
Gerhard "Or Maybe Check Their Website" Paseman, 2017.03.02.
A historical example, in the sense that the conjectural equality has been refuted: A180632 (Minimum length of a string of letters that contains every permutation of $n$ letters as sub-strings) was conjectured equal to A007489 ($\sum_{k=1}^n k!$).
The exact value of A180632 at $n=6$ is still unknown, but it must be less than the conjectured value of $1!+2!+\cdots+6!=873$, because the following string of length 872 contains every permutation of 123456 as a substring:
12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123
Best Answer
The number of divisions of $\mathbb{R}^3$ by $k \ge 0$ planes in general position starts 1,2,4,8, then 15, etc. For $\mathbb{R}^6$ it is 1,2,4,8,16,32,64 then 127. In general for $\mathbb{R}^N$ it is the sum of the binomial coefficients from $\binom{k}{0}$ up to $\binom{k}{N}$ and hence it agrees with $2^k$ for terms 0,1,2, up to N before starting to fall off.
other answers Of course for prime p, $2^{p-1}=1 \mod{p}$ but there are only 2 known cases $p=1093$ and $3511$ where $2^{p-1}=1 \mod{p^2}$. SO primes and primes with $2^{p-1} \ne 1 \mod{ p^2}$ agree for the first 182 primes.
For "listed in the OEIS" there are a couple which go from 1 to 99 then skip 100: undulating numbers in base 10 and cents you can have in US coins without having change for a dollar (the latter being 1-99 along with $105, 106, 107, 108, 109, 115, 116, 117, 118, 119$.)